Abstract:
A method for branch metric calculation in a plurality of communications standards is disclosed. The method generally includes steps (A) to (C). Step (A) may calculate a plurality of sum values by adding a plurality of first values related to a plurality of information bits, a plurality of second values related to the information bits and a plurality of third values related to a plurality of parity bits. Step (B) may generate a plurality of permutated values by permutating the sum values based on a configuration signal. The configuration signal generally identifies a current one of the communications standards. Step (C) may generate a plurality of branch metrics values by adding pairs of the permutated values.

Description:
This application claims the benefit of Russian Application No. 2010148337, filed Nov. 29, 2010 and is hereby incorporated by reference in its entirety. 
     FIELD OF THE INVENTION 
     The present invention relates to trellis decoding generally and, more particularly, to a method and/or apparatus for implementing a branch metrics calculation for multiple communications standards. 
     BACKGROUND OF THE INVENTION 
     Turbo and convolutional codes are widely used forward error correction codes. Turbo codes were proposed by Berrou and Glavieux in 1993 and have been adopted in many communication standards such as Wideband-CDMA (WCDMA), Code Division Multiple Access 2000 (CDMA2000), Worldwide Interoperability for Microwave Access (WiMAX), Long Term Evolution (LTE) and Digital Video Broadcasting-Return Channel via Satellite (DVB-RCS). The codes allow near optimal decoding with excellent performance approaching the Shannon limit for Additive White Gaussian Noise (AWGN) channels. 
     Conventional radix-4 decoding supports duo-binary turbo codes (adopted in WiMAX and DVB-RCS) and single-binary convolutional and turbo codes. Moreover, support for the duo-binary turbo codes implies two times faster decoding techniques than for single-binary codes at the expense of some additional circuit area. A problem with radix-4 decoding is a bottleneck in calculating the state metrics. A State Metrics Calculator (SMC) circuit performing add-compare-select operations experiences a bottleneck when implementing high-speed convolutional and turbo decoders. State metrics calculations cannot be easily pipelined because the state metrics computed at time instance t are used for computing the state metrics at time instance t+1. Therefore, radix-4 decoding increases the importance of the path through the SMC circuit. Another problem with radix-4 decoding is related with decoder universality (i.e., the ability to support many different convolutional and turbo codes in the same hardware). Since the trellises for the various codes are different, additional configuration logic (i.e., multiplexers) is commonly used in the SMC circuit to handle all of the trellises in a single design. 
     SUMMARY OF THE INVENTION 
     The present invention concerns a method for branch metric calculation in a plurality of communications standards. The method generally includes steps (A) to (C). Step (A) may calculate a plurality of sum values by adding a plurality of first values related to a plurality of information bits, a plurality of second values related to the information bits and a plurality of third values related to a plurality of parity bits. Step (B) may generate a plurality of permutated values by permutating the sum values based on a configuration signal. The configuration signal generally identifies a current one of the communications standards. Step (C) may generate a plurality of branch metrics values by adding pairs of the permutated values. 
     The objects, features and advantages of the present invention include providing a method and/or apparatus for implementing a branch metrics calculation for multiple communications standards that may (i) implement a configurable branch metrics calculator, (ii) avoid multiplexers in state metrics calculations, (iii) support multiple communications standards, (iv) implement a universal switch module and/or (v) occupy a low silicon area. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
         FIG. 1  is a block diagram of a convolutional rate 1/s encoder; 
         FIG. 2  is a block diagram of a convolutional turbo rate ⅓ encoder; 
         FIG. 3  is a block diagram of a Soft-In-Soft-Out decoder; 
         FIG. 4  is a block diagram of a convolutional rate ½ encoder; 
         FIG. 5  is a block diagram of a Maximum A Posteriori decoder; 
         FIG. 6  is a block diagram of a Viterbi decoder; 
         FIG. 7  is a diagram of an example trellis for a convolutional code; 
         FIG. 8  is a diagram of a radix-2 trellis and a radix-4 trellis; 
         FIG. 9  is a block diagram of a rate 1 convolutional encoder; 
         FIG. 10  is a diagram of a transition graph; 
         FIG. 11  is a block diagram of an Add-Compare-Select circuit; 
         FIG. 12  is a diagram of a universal dependence graph for state metrics calculation; 
         FIG. 13  is a block diagram of an apparatus in accordance with a preferred embodiment of the present invention; 
         FIG. 14  is a diagram of a state transition diagram; and 
         FIG. 15  is a block diagram of an example implementation of a universal switch circuit. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Some embodiments of the present invention generally concern a reconfigurable chip (or die) for decoding an input signal in accordance with two or more wireless communications standards. The wireless communications standards may include, but are not limited to, a Long Term Evolution (LTE) standard (3GPP Release 8), an Institute of Electrical and Electronics Engineering (IEEE) 802.16 standard (WiMAX), a Wideband-CDMA/High Speed Packet Access (WCDMA/HSPA) standard (3GPP Release 7) and a CDMA-2000/Ultra Mobile Broadband (UMB) standard (3GPP2). Other wired and/or wireless communications standards may be implemented to meet the criteria of a particular application. 
     Some embodiments of the present invention may relate to decoder universality where many different convolutional codes and turbo codes are supported in the same hardware. Instead of adding configuration logic to a State Metric Calculation (SMC) circuit, configuration logic may be added to a Branch Metric Calculation (BMC) circuit. The BMC circuit generally computes branch metrics and may be used with the SMC circuit in decoding. The BMC circuit may be readily pipelined. Hence, adding configuration logic to BMC circuit generally does not lead to a bottleneck. Moreover, implementations of some embodiments may utilize low silicon area and may be easily configured. Any rate (e.g., ⅓ rate) convolutional encoder with a given constraint length (e.g., up to 8) may be supported. Furthermore, a simple universal permutation 4×4-network may be used in the configuration logic to reduce the overall layout area. 
     The universal BMC circuit design generally includes a radix-4 universal branch metric calculation. The universal branch metric calculation may be used in both (i) Maximum-Logarithmic-MAP (Maximum A Posteriori) decoding techniques of turbo codes and (ii) Viterbi decoding techniques of convolutional codes. The universal branch metric calculations may also be used for high-speed and low-area implementations of multi-standard radix-4 decoders supporting turbo and convolutional decoding for most existing wireless standards, such as W-CDMA, CDMA2000, WiMAX and LTE. 
     Referring to  FIG. 1 , a block diagram of an apparatus  100  is shown. The apparatus (or device or circuit)  100  may implement a convolutional rate 1/s encoder. A signal (e.g., IN) may be received by the apparatus  100 . A signal (e.g., OUT) may be generated by the apparatus  100  in response to the signal IN. The apparatus  100  may represent one or more modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The signal IN may convey an information word received by the apparatus  100 . The information word “d” (e.g., data to be transmitted) may be described by formula 1 as follows:
 
 d =( d   1   , . . . , d   k )ε{0,1} k   (1)
 
where each diε{0,1} may be an information bit and parameter “k” may be an information word length. The apparatus  100  generally adds redundancy to the information word d and produces a codeword “c” in the signal OUT. Codeword c is generally illustrated by formula 2 as follows:
 
 c =( c   1   , . . . , c   n )ε{0,1} n   (2)
 
where “n” is the codeword length and R=k/n may be a code rate.
 
     For convolutional rate 1/s, the apparatus  100  may be defined by a generator matrix G. Generator matrix G is generally shown in formula 3 as follows:
 
 G=[g   (1) ( D ), . . . ,  g   (s) ( D )]  (3)
 
where each g(i)(D) (e.g., formula 4)
 
                       g     (   i   )       ⁡     (   D   )       =           a     (   i   )       ⁡     (   D   )           b     (   i   )       ⁡     (   D   )         ∈       F   2     ⁡     (   D   )                 (   4   )               
may be a rational function in variable D over the binary field F 2 ={0,1}. The elements a(i)(D), b(i)(D)εF 2 (D) may be polynomials in D with coefficients in F 2  and a(i)(0)=b(i)(0)=1. When the apparatus  100  receives the signal IN carrying an infinite binary sequence (e.g., formula 5)
 
 d=d   1   ,d   2   , . . . , d   i , . . .  (5)
 
the signal IN may be interpreted as a formal power series per formula 6 as follows:
 
 d ( D )= d   1   +d   2   D+ . . . +d   i   D   i−1 + . . .  (6)
 
The apparatus  100  may generate multiple signals (e.g., P 1  to PS). A combination of the signals P 1  to PS may form the signal OUT. Each signal P 1  to PS may carry a sequence (e.g., p( 1 ) to p(s)) as shown in formulae 7 set as follows:
 
                         p     (   1   )       =     p   1     (   1   )         ,     p   2     (   1   )       ,   …   ⁢           ,     p   i     (   1   )       ,   …     ⁢     
     ⁢           ⁢   ⋮   ⁢     
     ⁢         p     (   s   )       =     p   1     (   s   )         ,     p   2     (   s   )       ,   …   ⁢           ,     p   i     (   s   )       ,   …             (   7   )               
The sequences may be considered as formal power series and calculated as shown in formulae set 8 as follows:
 
                           p     (   1   )       ⁡     (   D   )       =         t   1     ⁡     (   D   )       ·     d   ⁡     (   D   )           ,     
     ⁢           ⁢   ⋮     ⁢     
     ⁢           p     (   s   )       ⁡     (   D   )       =         t   s     ⁡     (   D   )       ·     d   ⁡     (   D   )           ,             (   8   )               
The resulting codeword c may be represented by formula 9 as follows:
 
 c =( p   1   (1)   , . . . , p   1   (s)   ,p   2   (1)   , . . . , p   2   (s)   , . . . , p   k   (1)   , . . . , p   k   (s)   (9)
 
where p(j) (e.g., formula 10)
 
 p   (j) =( p   1   (j)   , . . . , p   k   (j) )  (10)
 
may be the j-th element created by the convolutional encoding. The word p(j) may be referred to as a parity word.
 
     In the case of convolutional codes (CC) generally used in wireless standards, the channel encoding may not be systematic (e.g., the encoding may have a polynomial transfer matrix). In the case of convolutional turbo codes (CTC), the encoding may be systematic (e.g., the information word d may be a part of the codeword c). 
     Referring to  FIG. 2 , a block diagram of an apparatus  102  is shown. The apparatus (or device or circuit)  102  may implement a convolutional turbo rate ⅓ encoder. The apparatus  102  generally comprises a circuit (or module)  104 , a circuit (or module)  106  and a circuit (or module)  108 . The signal. IN may be received by the circuits  104  and  108 . A signal (e.g., PER) may be generated by the circuit  108  and received by the circuit  106 . The circuit  104  may generate the signal P 1 . The circuit  106  may generate the signal P 2 . A combination of the signals IN, P 1  and P 2  may establish the signal OUT. The circuits  104  to  108  may represent modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The circuit  104  may implement a Recursive Systematic Convolutional (RSC) encoder. The circuit  104  is generally operational to encode the information word d to generate the parity word p( 1 ). The information word d may be received in the signal IN. The parity word p( 1 ) may be presented in the signal P 1 . The encoding may be a recursive systematic convolutional encoding. 
     The circuit  106  may implement another RSC encoder. The circuit  106  is generally operational to encode a permuted word π(d) (e.g., formula 11)
 
π( d )=( d   π(1)   , . . . , d   π(k) )  (11)
 
to generate the parity word p( 2 ). The permuted word π(d) may be received in the signal PER from the circuit  108 . The parity word p( 2 ) may be presented in the signal P 2 . The encoding may also be a recursive systematic convolutional encoding. The circuit  106  may be a duplicate of the circuit  104  and perform the same encoding technique.
 
     The circuit  108  may implement an interleaver circuit. The circuit  108  is generally operational to generated the permuted word π(d) by permutating the information word d. The information word d may be received in the signal IN. The permuted word π(d) may be presented to the circuit  106  in the signal PER. 
     Each standard LTE, W-CDMA/HSPA and WiMAX may include rate ⅓ turbo codes. In the WiMAX standard, the codeword c may be given by formula 12 as follows:
 
 c =( d   1   ,p   1   (1)   ,p   1   (2)   , . . . , d   k   ,p   k   (1)   ,p   k   (2) )  (12)
 
where n=3k and tail-biting may be utilized. In the LTE standard and the W-CDMA/HSPA standard, the codeword c is generally illustrated by formula 13 as follows:
 
 c =( d   1   ,p   1   (1)   ,p   1   (2)   , . . . , d   k   ,p   k   (1)   ,p   k   (2)   ,t   1   , . . . , t   12 )  (13)
 
where n=3k+12 and the final several bits (e.g., 12 bits t 1 , . . . , t 12 ) may be used for trellis termination. The trellis termination generally forces the apparatus  102  to an initial zero state. In the case of trellis termination, the actual code rate k/(3k+12) may be a little smaller than the rate ⅓.
 
     In the above cases, the parity word p( 1 ) in the signal P 1  may convey the parity bits word obtained for an unpermuted information word d generated by the circuit  104 . The parity word p( 2 ) may be obtained for the permuted word π(d) generated by the circuit  108 . An operation n may be a permutation on a set {1, 2, . . . , k} specified by an interleaver table of the standard. 
     A decoder is generally a device that receives vector of quantized Logarithm of Likelihood Ratios (LLR&#39;s) for each bit in the codeword c as received from a modulator. The modulator operation may be denoted by L(c). The decoder generally attempts to reconstruct the transmitted information word d. A decision of the decoder may be denoted by a {circumflex over (d)} per formula 14 as follows:
 
 {circumflex over (d)} =( {circumflex over (d)}   1   , . . . , {circumflex over (d)}   k )ε{0,1} k   (14)
 
Each value {circumflex over (d)} i  may be called a hard decision for information bit {circumflex over (d)} i , where i=1 to k. Sometimes (e.g., in turbo equalization) the decoder may also generate soft decisions for the information and the parity bits. Such decoders may be called soft-input soft-output (SISO) decoders.
 
     Referring to  FIG. 3 , a block diagram of an apparatus  120  is shown. The apparatus (or device or circuit)  120  may implement a Soft-In-Soft-Out (SISO) decoder for convolutional turbo rate ⅓ codes with a Hard Decision Aided (HDA) early stopping criteria. The apparatus  120  generally comprises a circuit (or module)  122 , a circuit (or module)  124 , multiple interleaver circuits (or modules)  126   a  to  126   b , multiple inverse interleaver circuits (or modules)  128   a  to  128   b , multiple slicer circuits (or modules)  130   a  to  130   b  and a compare circuit (or module)  132 . The circuits  122  to  132  may represent modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     A signal (e.g., LIN(D)) may be received by the circuits  122 ,  124  and  126   a . A signal (e.g., LIN(P 1 )) may be received by the circuit  122 . A signal (e.g., LIN(P 2 )) may be received by the circuit  124 . The circuit  128   a  may generate a signal (e.g., LOUT(D)). A signal (e.g., LOUT(P 1 )) may be generated by the circuit  122 . The circuit  124  may generate a signal (e.g., LOUT(P 2 )). A signal (e.g., STOP/CONT) may be generated by the circuit  132 . 
     Turbo decoding may perform a number of computation cycles called full iterations. Each full iteration may include two half iterations. The turbo decoding process generally runs until either a maximum full iteration number (e.g., typical value is 8) is reached or one or more early stopping criterion is satisfied. 
     On each half iteration, the circuits  122  and  124  generally perform a Maximum A Posteriori (MAP) process explained below for one of the constitutive convolutional encoders RCS 1  and RSC 2  of a turbo encoder (see  FIG. 2 ). For each full iteration on the initial half iteration, the circuits  122  and  124  generally perform MAP decoding for RSC 1  and on the second half iteration for RSC 2 . Extrinsic LLR&#39;s obtained in the circuits  122  and  124  may be permuted by the circuits  128   b / 126   b  and exchanged between half iterations. After each half iteration, the circuit  132  may compare hard decisions from the circuit  122  with permuted hard decisions from the circuit  124 . If the hard decisions match each other, the circuit  120  may stop decoding and assert the signal STOP/CONT in a stop condition. Otherwise, the signal STOP/CONT may be asserted in a continue condition. The matching hard decision criterion may be an early stopping criterion called hard-decision aided (HDA) criterion. 
     Referring to  FIG. 4 , a block diagram of an apparatus  140  is shown. The apparatus (or device or circuit)  140  may implement a convolutional rate ½ encoder. The apparatus  140  generally comprises a circuit (or module)  142 . The circuit  140  may represent one or more modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The signal IN may be received by the circuit  142 . The circuit  142  may generate a signal (e.g., P). The signal OUT may be a combination of the signals IN and a signal (e.g., P). 
     The circuit  140  may be operational to generate a systematic convolutional rate ½ code. The circuit  142  may implement another RSC circuit, similar to circuits  104  and  106 . The circuit  142  may be operational to generate a parity word p in the signal P in response to the information word d received in the signal IN. 
     Referring to  FIG. 5 , a block diagram of an apparatus  150  is shown. The apparatus (or device or circuit)  150  may implement a MAP decoder for systematic convolutional rate ½ codes. The circuit  150  may represent one or more modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     A signal (e.g., LIN(D)) may be received by the circuit  150  from a modulator. A signal (e.g., LIN(P)) may also be received by the circuit  150  from the modulator. Another signal (e.g., LA(D)) may be sent from the modulator to the circuit  150 . The circuit  150  may generate a signal (e.g., LOUT(D)). A signal (e.g., LOUT(P)) may also be generated by the circuit  150 . A signal (e.g., LE(D)) may be generated by the circuit  150 . 
     The circuit  150  may implement a MAP decoder circuit. A part of the turbo decoding process is the MAP decoding process. The MAP decoding process may be applied for any convolutional code. In the case of rate ⅓ turbo code, the MAP decoding may be applied for systematic convolutional rate ½ codes only. In some embodiments, the circuit  150  may be operational to perform a Max-Log-MAP decoding process. Other MAP decoding processes may be implemented to meet the criteria of a particular application. 
     The signal LIN(D) may carry an LLR soft decision from the modulator for the information bits d. The signal LIN(P) may convey an LLR soft decision for the parity bits p. The signal LA(D) generally carries LLR soft decision a priori probability data for the information bits d. LLR soft decisions of MAP decoder (circuit  150 ) may be carried in the signal LOUT(D) for the information bits d and the signal LOUT(P) for the parity bits p. Extrinsic LLR data used in turbo decoding between half iterations may be presented in the signal LE(D). 
     Referring to  FIG. 6 , a block diagram of an apparatus  160  is shown. The apparatus (or device or circuit)  160  may implement a Viterbi decoder for convolutional rate ⅓ codes. The circuit  160  may represent one or more modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The signal LIN(D) may be received by the circuit  160  from a modulator. Multiple signals for parity (e.g., LIN(P 1 ), LIN(P 2 ) and LIN(P 3 )) may also be received by the circuit  160  from the modulator. The circuit  160  may generate a signal (e.g., D). A signal (e.g., P 1 ) may also be generated by the circuit  160 . A signal (e.g., P 2 ) may be generated by the circuit  160 . The circuit  160  may also generate a signal (e.g., P 3 ). 
     The circuit  160  may implement a Viterbi decoder circuit. The circuit  160  is generally operational to decode according to the Viterbi decoding process. The Viterbi process is generally used for decoding of convolutional codes. The same hardware may be utilized for performing state metric recursions in both the Viterbi process and the MAP decoding process (e.g., circuit  150 ). The circuit  160  generally uses LLR soft decisions from the modulator for information bits d and parity bits p as received in the signals LIN(D), LIN(P 1 ), LIN(P 2 ) and LIN(P 3 ). The result of Viterbi decoder work may be the hard decisions for the reconstructed information bits {circumflex over (d)} and the reconstructed parity bits {circumflex over (p)}. The hard decisions may be carried in the signals D, P 1 , P 2  and P 3  respectively. 
     Referring to  FIG. 7 , a diagram of an example trellis  170  for a convolutional code is shown. Both the Max-Log-MAP decoding process and the Viterbi decoding process generally use a graphical representation of the code called a code trellis. The code trellis generally describes the convolutional encoder work in a time scale. If a codeword length is “n”, the trellis  170  may be a graph with n+1 groups of vertexes V 0 , V 1 , . . . , V n , called levels. Each level Vi generally corresponds to a time instance t=0, 1, . . . , n and may include all possible encoder states at time instance t. Therefore, vertex V 0  may contain only an initial encoder state q 0 , vertex V 1  may contain all the states of encoder that are reachable in one step from q 0 , and so on. Given an edge e from a state qεVi labeled with x/y to a state q′εVi, if an encoder at the state q responds to an input x by moving to state q′ and outputs y. The edge e from the state q to the state q′ in the trellis  170  may be denoted by 
     
       
         
           
             
               q 
               ⁢ 
               
                 ⟶ 
                 e 
               
               ⁢ 
               
                 q 
                 ′ 
               
             
             . 
           
         
       
     
     Referring to  FIG. 8 , a diagram of an example of a radix-2 trellis  172  and a radix-4 trellis  174  is shown. To support WiMAX standard a radix-4 decoding process may be implemented. In some embodiments, the radix-4 trellis  174  may represent the work of encoder with double speed. A radix-4 variant of the trellis  174  generally operates two times faster than the ordinary radix-2 trellis  172 . 
     Both the Max-Log-MAP decoding process for turbo decoding and the Viterbi decoding process for convolutional decoding may be based on the same procedure. The procedure generally computes (i) for each edge e in the code trellis a quantity γ(e) called a branch metric and (ii) for each vertex q in each level Vi of the code trellis a number of quantities called state metrics: α t (q) and β t (q) in Max-Log-MAP decoding; and α t (q) in Viterbi decoding. All the quantities may be in the domain R∪{∞}, where R may be the set of real numbers. In hardware implementations of a decoder, integer arithmetic may be used instead of real numbers. 
     In the case of Max-Log-MAP decoding, the computation for trellis of length n may be as illustrated in formulae 15 to 18 as follows: 
                         α   0     ⁡     (     q   0     )       =   0     ,       and   ⁢           ⁢       α   0     ⁡     (   q   )         =         -   ∞     ⁢           ⁢   for   ⁢           ⁢   all   ⁢           ⁢   encoder   ⁢           ⁢   states   ⁢           ⁢   q     ≠     q   0                 (   15   )                     α     t   +   1       ⁡     (     q   ′     )       =         max     e     q   ⟶     q   ′           ⁢       {         α   t     ⁡     (   q   )       +     γ   ⁡     (   e   )         }     ⁢           ⁢   for   ⁢           ⁢   all   ⁢           ⁢   t       =   0       ,   1   ,   …   ⁢           ,   n           (   16   )                   β   0     ⁡     (   q   )       =     0   ⁢           ⁢   for   ⁢           ⁢   all   ⁢           ⁢   encoder   ⁢           ⁢   states   ⁢           ⁢   q             (   17   )                     β   t     ⁡     (   q   )       =         max     e     q   ⟶     q   ′           ⁢       {         β     t   +   1       ⁡     (     q   ′     )       +     γ   ⁡     (   e   )         }     ⁢           ⁢   for   ⁢           ⁢   all   ⁢           ⁢   t       =   0       ,   1   ,   …   ⁢           ,   n   ,           (   18   )               
where q 0  may be an initial state of the encoder. In the case of Viterbi decoding, a recursion for α state metrics may be implemented. Furthermore, for each computed α t+1 (q′), the edge e should be remembered such that α t (q)+γ(e) are maximal.
 
     The branch metrics for edge e in a radix-4 Max-Log-MAP decoding for turbo codes is generally computed by formula 19 as follows:
 
γ( e )=(−1) x     1   ( X   1   +A   1 )+(−1) x     2   ( X   2   +A   2 )+(−1) z     1     Z   1 +(−1) z     1     Z   1   (19)
 
where x 1  and x 2  may be information bits, and z 1  and z 2  may be parity bits associated with the edge e. Branch metrics calculations may include (i) a priori soft LLR values A 1 ,A 2  for information bits x 1 ,x 2  from the signal LA(D), (ii) soft LLR values X 1 ,X 2  for information bits x 1 ,x 2  from the signal LIN(D) and (iii) soft LLR values Z 1 ,Z 2  for parity bits z 1 ,z 2  from the signal LIN(P).
 
     Branch metrics for edge e in radix-4 Viterbi decoding process for rate ⅓ convolutional code may be computed by formula 20 as follows: 
                     γ   ⁡     (   e   )       =       ∑     i   =   1     s     ⁢     (           (     -   1     )       z   1     (   i   )         ⁢     Z   1     (   i   )         +         (     -   1     )       z   2     (   i   )         ⁢     Z   2     (   i   )           )               (   20   )               
Parity bits z 1 ( i ),z 2 ( i ) may be associated with the edge e and soft LLR values Z 1 (i),Z 2 (i) from the signal LIN(P) may be used (see for the case s=3). When all of the state and branch metrics are computed, the decoders generally produce soft LLR decisions in the signals LOUT(D), LOUT(P) for the information bits and the parity bits respectively and extrinsic LLR&#39;s in the signal LE(D) in the Max-Log-MAP decoding process (e.g., circuit  150 ) and hard decisions in the signals D, P( 1 ), . . . , P(s) in the Viterbi decoding process (e.g., circuit  160 ).
 
     Referring to  FIG. 9 , a block diagram of an apparatus  180  is shown. The apparatus (or device or circuit)  180  may implement a rate 1 convolutional encoder. The apparatus  180  generally represents a scheme for an RSC encoder. The apparatus  180  generally comprises a circuit (or module)  182 , multiple circuits (or modules)  184   a  to  184   m , multiple circuits (or modules)  186   a  to  186   m , multiple circuits (or module)  188   a  to  188   m , multiple circuits (or modules)  190   a - 190   m  and multiple circuits (or modules)  192   a  to  192   m - 1 . The circuit  182  may receive the signal IN. The circuit  188   m  may generate and present the signal OUT. The circuits  182  to  192   m - 1  may represent modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The circuit  182  may present a signal to the circuit  184   a  and the circuit  188   a . Each circuit  184   a  to  184   m - 1  may present a signal to the next respective circuit  184   b  to  184   m , a respective circuit  186   a  to  186   m - 1  and a respective circuit  190   a  to  190   m - 1 . The circuit  184   m  may present a signal to the circuits  186   m  and  190   m . Each circuit  186   a  to  186   m  may present a signal to a respective circuit  188   a  to  188   m . Each circuit  188   a  to  188   m - 1  may present a signal to a respective next circuit  188   b  to  188   m . Each circuit  190   a  to  190   m - 1  may present a signal to a respective circuit  192   a  to  192   m - 1 . The circuit  190   m  may also present a signal to the circuit  192   m - 1 . Each circuit  192   b  to  192   m - 1  may present a signal to a respective previous circuit  192   a  to  192   m - 2 . The circuit  192   a  may present a signal back to the circuit  182 . 
     Each circuit  182 ,  188   a  to  188   m  and  192   a  to  192   m - 1  may implement an adder circuit. The circuits  182 ,  188   a  to  188   m  and  192   a  to  192   m - 1  are generally operational to generate a sum at an output port of two values received at the respective input ports. 
     Each circuit  184   a  to  184   m  may implement a delay circuit (e.g., register). The circuit  184   a - 184   m  may be operational to buffer a received value for a single clock cycle. 
     Each circuit  186   a  to  186   m  may implement a transfer circuit. The circuit  186   a  to  186   m  may be operational to transfer an input value to an output value per a respective polynomial (e.g., A 1  to Am). 
     Each circuit  190   a  to  190   m  may implement another transfer circuit. The circuit  190   a  to  190   m  may be operational to transfer an input value to an output value per a respective polynomial (e.g., B 1  to Bm). A number of additional rates may be easily obtained by applying puncturing. Puncturing generally deletes some of the parity symbols according to a puncturing scheme defined in each standard. 
     Trellises of different convolutional codes generally have similar structure. The similarities may enable a reduction in the complexity of a universal trellis decoder suitable for working with many trellises. Consider a rate 1 convolutional encoder where a state transition of any rate 1/s encoder is the same. An encoder state q may be defined by formula 21 as follows:
 
 q ( t )=[ q   1 ( t ), . . . ,  q   m ( t )]ε F   2   m   (21)
 
where x(t)εF 2 , and y(t)εF 2  are an input and output at the moment t=0, 1, . . . . Choosing an initial state q( 0 ) of the encoder per formula 22 as follows:
 
 q   (0)   =[q   1   (0)   , . . . , q   m(0)   ]εF   2   m   (22)
 
the work of the encoder may be described by formula 23 as follows:
 
                   {             q   1     ⁡     (   0   )           =           q   1     (   0   )       ,                         ⋮                           q   m     ⁡     (   0   )           =           q   m     (   0   )       ,                 q   1     ⁡     (     t   +   1     )           =               b   1     ⁢       q   1     ⁡     (   t   )         +   …   +       b   m     ⁢       q   m     ⁡     (   t   )         +     x   ⁡     (   t   )         ,                 q   2     ⁡     (     t   +   1     )           =             q   1     (   t   )     ,                         ⋮                           q   m     ⁡     (     t   +   1     )           =             q     m   -   1       (   t   )     ,               y   ⁡     (   t   )           =             a   0     ⁢     x   ⁡     (   t   )         +       a   1     ⁢       q   1     ⁡     (   t   )         +   …   +       a   m     ⁢       q   m     ⁡     (   t   )                         (   23   )               
and in a compact form by formula 24 as follows:
 
                   {           q   ⁡     (   0   )           =           q     (   0   )       ,               q   ⁡     (     t   +   1     )           =           δ   ⁡     (       q   ⁡     (   t   )       ,     x   ⁡     (   t   )         )       ,               y   ⁡     (   t   )           =           λ   ⁡     (       q   ⁡     (   t   )       ,     x   ⁡     (   t   )         )       ,             t       =         0   ,   1   ,   2   ,   …                   (   24   )               
A transition function may be described by formula 25 as follows:
 
δ: F   2   m   ×F   2   →F   2   m   (25)
 
An output function of finite automaton that corresponds to the encoder may be given by formula 26 as follows:
 
λ: F   2   m   ×F   2   →F   2   (26)
 
     Referring to  FIG. 10 , a diagram of a transition graph  200  for a radix-4 convolutional encoder is shown. The transition graph  200  generally illustrates possible transitions from a state q(t) to a state q(t+2). 
     Returning to formula 23, if bm=1, the automata may be seen as a permutation automata. In a permutation automata, each input xεF 2  may permute the set of states F 2 . If a 0 =1, the formula 27 as follows:
 
 y ( t )= a   0   x ( t )+ a   1   q   1 ( t )+ . . . + a   m   q   m ( t )  (27)
 
generally shows that if q(t) is fixed then y(t) is either x(t) or  x (t). In such a case, the input/output function of the automaton may be a bijection. In a bijection, for any two different input words and fixed initial state the corresponding outputs may be different. From the above, an encoder generally satisfies the following condition: for any two different input words of length no more than m, the different input words may map an initial state into different states. Notice that all of the turbo encoders from the WiMAX, LTE and WCDMA communications standards may satisfy the following two conditions (bm=1 and a 0 =1). Convolutional encoders generally do not meet the bm=1 condition. Consider a set of four states as illustrated in formula 28 as follows:
 
             q   1    . . . q   m-2   **             :={q   1    . . . q   m-2 00 ,q   1    . . . q   m-2 01 ,q   1    . . . q   m-2 10 ,q   1    . . . q   m-2 11}  (28)
 
By applying a set of input words {00,01,10,11}, a set described by formula 29 may be obtained as follows:
 
           **q   1    . . . q   m-2             :={ 00 q   1    . . . q   m-2 ,01 q   1    . . . q   m-2 ,10 q   1    . . . q   m-2 ,11 q   1    . . . q   m-2 }  (29)
 
Moreover, the corresponding transition graph  200  may be a full bipartite graph K 4,4 .

     Referring to  FIG. 11 , a block diagram of an apparatus  220  is shown. The apparatus (or device or circuit)  220  may implement an Add-Compare-Select (ACS) circuit for state metrics calculations. The circuit  220  generally comprises multiple adders (or modules)  222   a  to  222   d  and a circuit (or module)  224 . The circuits  222   a  to  224  may represent one or more modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     A signal (e.g., SM 0 ) and a signal (e.g., BM 0 ) may be received by the circuit  222   a . The circuit  222   b  may receive a signal (e.g., SM 1 ) and a signal (e.g., BM 1 ). A signal (e.g., SM 2 ) and a signal (e.g., BM 2 ) may be received by the circuit  222   c . The circuit  222   d  may receive a signal (e.g., SM 3 ) and a signal (e.g., BM 3 ). The circuit  224  may receive the sums from the circuits  222   a  to  222   d . A signal (e.g., IND) may be generated by the circuit  224 . The circuit  224  may also generate a signal (e.g., SM). 
     As may be seen from the formulae for the state metrics (α and β) computations in the Max-Log-MAP decoding and the Viterbi decoding, a common operation used is a maximum of a number of sums. In the case of a radix-4 trellis, the maximum number may be 4. In hardware, the computations may be performed in an add-compare-select circuit (e.g., circuit  220 ). 
     The circuits  222   a  to  222   d  may implement adder circuits. Each circuit  222   a  to  222   d  may be operational to add a branch metric value and a respective state metric value. The sums may be the “add” portion of the add-compare-select operations. 
     The circuit  224  may implement a compare and select circuit. The circuit  224  is generally operational to compare the sum values calculated by the circuits  222   a  to  222   d . The circuit  224  may also be operational to select a maximum sum value from among the sum values. The selected maximum sum value may be presented in the signal SM as a new state metric value. The new state metric value may be computed per formula 30 as follows: 
                   SM   =       max     i   ∈     {     0   ,           ⁢   …   ⁢           ,   3     }         ⁢     {       SM   i     +     BM   1       }               (   30   )               
An index value iε{0, . . . , 3} of the selected maximum sum value may be presented in the signal IND.
 
     Referring to  FIG. 12 , a diagram of a universal dependence graph  230  for state metrics calculation is shown. The graph  230  generally comprises a number (e.g., 8) of states (e.g., 000, 001, 010, 011, 100, 101, 110 and 111). Each state may have two transitions leaving to other states. Each state may have either (i) 4 transitions entering from other states or (ii) 3 transitions entering from other states and a single transition remaining within the state. 
     Consider a convolutional code with 256 states. A transition graph (e.g., transition graph  200 ) generally has 64 K 4,4  components and each component may be processed in parallel in the Viterbi decoding. In the case of turbo codes, subgraphs generally cannot be process in parallel because the state metrics are calculated in each clock cycle. Therefore, the universal dependence graph  230  may be implemented according to the encoder state transition graph (e.g., transition graph  200 ). By way of example, the graph  230  generally illustrates transitions to the state 110 (e.g., having a zero last bit) from the states 000, 001, 010, 011 (e.g., each having a zero initial bit). 
     To construct a state metrics calculation circuit, each vertex of the dependent graph  230  may be associated with the circuit  220 . The circuits  220  may be inter-connected according to the transitions of the dependent graph  230  to obtain a state metric calculator (SMC) for radix-4 trellis decoding. Each vertex of the dependent graph  230  generally has incoming transitions of degree 4. 
     Consider a high-speed turbo decoder that calculates state metrics for vertexes in a level V t  of the trellis in parallel in single clock cycle. The state metrics obtained for the level V t  may be used on the next clock cycle for computations of state metrics in next level V t+1 . Therefore, the SMC generally cannot be pipelined. For encoders used in different communications standards, different trellises may be used and so multiplexers may be implemented at the input ports of the ACS circuits in some designs. However, the dependence graphs for several communications standards, such as W-CDMA, LTE, CDMA2000 and WiMAX, may be isomorphic to the dependence graph  230  shown in  FIG. 12 . Therefore, instead of using multiplexers at the input ports of the ACS circuit, some embodiments of the present invention may implement a configurable Branch Metrics Calculator. The configurable BMC generally calculates branch metrics (©) and permutes the branch metrics according to the communications standard. 
     Referring to  FIG. 13 , a block diagram of an apparatus  240  is shown in accordance with a preferred embodiment of the present invention. The apparatus (or device or circuit)  240  may implement a universal (configurable) branch metrics calculator circuit. The circuit  240  generally comprises multiple circuits (or modules)  242   a  to  242   b , multiple circuits (or modules)  244   a  to  244   b , multiple circuits (or modules)  246   a  to  246   h  and multiple circuits (or modules)  248   a  to  248   h . The circuits  242   a  to  248   h  may represent modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The circuit  242   a  may receive a signal (e.g., X 1 ) and a signal (e.g., A 1 ). The circuit  242   b  may receive a signal (e.g., X 2 ) and a signal (e.g., A 2 ). A signal (e.g., Z 1 ) may be received by the circuit  244   b . A signal (e.g., Z 2 ) may also be received by the circuit  244   b . A sum of the signals X 1  and A 1  may be presented from the circuit  242   a  to the circuit  244   a . A sum of the signals X 2  and A 2  may be presented from the circuit  242   b  to the circuit  244   a . The circuit  244   a  may generate a sum value that is presented to the circuits  246   a  to  246   d . The circuit  244   b  may generate a sum value that is presented to the circuits  246   e  to  246   h . A signal (e.g., CONF) may be received by each circuit  246   a  to  246   h . Each circuit  248   a  to  248   h  may receive a permuted value from different pairs of the circuits  246   a  to  246   h . A signal (e.g., BM) may be created by a combination of the sum values generated by the circuits  248   a  to  248   h.    
     The signals X 1 , X 2  may convey soft LLR values for the information bits x 1 ,x 2 . The signals A 1 ,A 2  may carry a priori soft LLR values for the information bits x 1 ,x 2 . The signals Z 1 ,Z 2  may carry soft LLR values for the parity bits z 1 ,z 2 . By way of example, each soft value may have a bit-width of w. The signal CONF may carry configuration information that identifies a particular communications standard from among several communications standards that the circuit  240  may process. 
     Each circuit  242   a  to  242   b  may implement an adder circuit. The circuits  242   a  to  242   b  may be operational to add the soft LLR values received in the respective signals X 1 ,A 1  and X 2 ,A 2  to calculate a sum value. 
     Each circuit  244   a  to  244   b  may implement a universal sum circuit. The circuits  244   a  to  244   b  are generally operational to calculate several (e.g., 4) output values (e.g., Y 00 , Y 01 , Y 10 , Y 11 ) from multiple (e.g., 2) input values (e.g., R 0 , R 1 ). The output values may be calculated according to formula 31 as follows:
 
 Y   x     0     x     1   =(−1) x     0     R   0 +(−1) x     1     R   1   (31)
 
where x 0 x 1 ε{00,01,10,11}.
 
     Each circuit  246   a  to  246   h  may implement a universal switch (USW) circuit. The circuits  246   a  to  246   h  may by operational to permute the output values received from the circuits  244   a  to  244   b  to generate the permuted values presented to the circuits  248   a  to  248   h . Control of the permutations may be provided through the signal CONF. The signal CONF generally comprises multiple control bits (e.g., a different set of bits σ, σ 0 , σ 1  for each circuit  246   a  to  246   h ). Each permutation generally corresponds to the permutation that performs on set {00,01,10,11} finite state automaton. 
     Referring to  FIG. 14 , a diagram of a state transition diagram  260  is shown. The finite state automation may be performed in accordance with the state transition diagram  260 . For each communications standard, a set of permutations (σ, σ 0 , σ 1 ) may be defined (e.g., a respective permutation for each of the circuits  246   a  to  246   h ). For eight circuits  246   a  to  246   h , a width of the signal CONF may be 3×8=24 bits. 
     Returning to  FIG. 13 , the permutations of the circuits  246   a  to  246   h  may generate XSW ij  (the j-th output of i-th circuit  246   a  to  246   h  connected to the circuit  244   a ) and ZSW ij  (the j-th output of i-th circuit  246   a  to  246   h  connected to the circuit  244   b ), for i=0, . . . , 7 and j=0, . . . , 3. 
     Each circuit  248   a  to  248   h  may implement an adder circuit. The circuits  248   a  to  248   h  are generally operational to add the permuted values received from the circuits  246   a  to  246   h  to generate the branch metrics values. The branch metrics value may be calculated according to formula 32 as follows:
 
 BM   ij   =XSW   ij   +ZSW   ij   , i= 0, . . . , 7 ; j= 0, . . . , 3  (32)
 
in which BM ij  may be a branch metric that corresponds to the j-th clockwise edge from i-th state (in binary representation A 2 A 1 A 0 ) on the dependence graph  230  A combination of the individual branch metrics values may be presented in the signal BM.
 
     The circuit  240  may be pipelined. For example, an initial pipeline stage may be created with the circuits  242   a ,  242   b ,  244   a  and  244   b . A next pipeline stage may be formed with the circuits  246   a  to  246   h  and  248   a  to  248   h . Other pipeline arrangements may be implemented to meet the criteria of a particular application. Therefore, the circuit  240  generally does not restrict a performance of the decoder. 
     Referring to  FIG. 15 , a block diagram of an example implementation of the circuit  246   a  is shown. The implementation may also be applicable to the other circuits  246   b  to  246   h . The circuit  246  generally comprises a circuit (or module)  282 , a circuit (or module)  284  and a circuit (or module)  286 . The circuit  246   a  may implement a universal permutations 4×4-network. The circuits  282  to  286  may represent modules and/or blocks that may be implemented as hardware, firmware, software, a combination of hardware, firmware and/or software, or other implementations. 
     The circuit  282  may receive the values Y 00  and Y 01  from the circuit  244   a  and the value σ 0  from the signal CONF. The values Y 10  and Y 11  may be received by the circuit  284  from the circuit  244   a  and the value σ 1  from the signal CONF. The circuit  286  may receive the permuted values from the circuits  282  and  284 . The circuit  286  may also receive the value σ from the signal CONF. Permuted signals (e.g., Y′ 00 , Y′ 01 , Y′ 10  and Y′ 11 ) may be generated by the circuit  286  and presented to the circuits  248   a  to  248   h.    
     Each circuit  282 ,  284  and  286  may implement a multiplexer circuit. The circuit  282  may be operational to permute the values Y 00  and Y 01  in response to the value σ 0 . While the value σ 0  is a logical 1, the values Y 00  and Y 01  may be passed straight through. While the value σ 0  is a logical 0, the values Y 00  and Y 01  may be exchanged. The circuit  284  may be operational to permute the values Y 10  and Y 11  in response to the value σ 1 . While the value of is a logical 1, the values Y 10  and Y 11  may be passed straight through. While the value σ 1  is a logical 0, the values Y 10  and Y 11  may be exchanged. The circuit  286  may be operational to permute the values received from the circuits  282  and  284  in response to the value σ. While the value σ is a logical 1, (i) the values received from the circuit  282  may be passed straight through as the values Y′ 00  and Y′ 01  and (ii) the values received from the circuit  284  may be passed straight through as the values Y′ 10  and Y′ 11 . While the value σ is a logical 0, the two values received from the circuit  282  may be exchanged with the two values received from the circuit  284 . The resulting permutation for each value Y 00 , Y 01 , Y 10  and Y 11  is generally illustrated by the state transition diagram  260 . 
     Some embodiments of the present invention may implement a configurable BMC circuit instead of implementing multiplexers at the input ports of the ACS circuit. The configurable BMC circuit generally supports multiple communications standards. An ordinary way to support multiple standards in single decoder is to implement multiplexers in a SMC circuit along a main path through the decoder. By using the configurable BMC circuit, the main path through the SMC circuit may be free from the multiplexers. Furthermore, the universal switch circuits used in the BMC circuit generally occupy a low silicon area, but at the same time may support any permutations of branch metrics arising in various wired and/or wireless communications standards. 
     The functions performed by the diagrams of  FIGS. 1-15  may be implemented using one or more of a conventional general purpose processor, digital computer, microprocessor, microcontroller, RISC (reduced instruction set computer) processor, CISC (complex instruction set computer) processor, SIMD (single instruction multiple data) processor, signal processor, central processing unit (CPU), arithmetic logic unit (ALU), video digital signal processor (VDSP) and/or similar computational machines, programmed according to the teachings of the present specification, as will be apparent to those skilled in the relevant art(s). Appropriate software, firmware, coding, routines, instructions, opcodes, microcode, and/or program modules may readily be prepared by skilled programmers based on the teachings of the present disclosure, as will also be apparent to those skilled in the relevant art(s). The software is generally executed from a medium or several media by one or more of the processors of the machine implementation. 
     The present invention may also be implemented by the preparation of ASICs (application specific integrated circuits), Platform ASICs, FPGAs (field programmable gate arrays), PLDs (programmable logic devices), CPLDs (complex programmable logic device), sea-of-gates, RFICs (radio frequency integrated circuits), ASSPs (application specific standard products), one or more monolithic integrated circuits, one or more chips or die arranged as flip-chip modules and/or multi-chip modules or by interconnecting an appropriate network of conventional component circuits, as is described herein, modifications of which will be readily apparent to those skilled in the art(s). 
     The elements of the invention may form part or all of one or more devices, units, components, systems, machines and/or apparatuses. The devices may include, but are not limited to, servers, workstations, storage array controllers, storage systems, personal computers, laptop computers, notebook computers, palm computers, personal digital assistants, portable electronic devices, battery powered devices, set-top boxes, encoders, decoders, transcoders, compressors, decompressors, pre-processors, post-processors, transmitters, receivers, transceivers, cipher circuits, cellular telephones, digital cameras, positioning and/or navigation systems, medical equipment, heads-up displays, wireless devices, audio recording, storage and/or playback devices, video recording, storage and/or playback devices, game platforms, peripherals and/or multi-chip modules. Those skilled in the relevant art(s) would understand that the elements of the invention may be implemented in other types of devices to meet the criteria of a particular application. 
     As would be apparent to those skilled in the relevant art(s), the signals illustrated in  FIGS. 11 ,  12  and  15  represent logical data flows. The logical data flows are generally representative of physical data transferred between the respective blocks by, for example, address, data, and control signals and/or busses. The system represented by the apparatuses  220 ,  240  and  246   a  may be implemented in hardware, software or a combination of hardware and software according to the teachings of the present disclosure, as would be apparent to those skilled in the relevant art(s). 
     While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the scope of the invention.