Patent Publication Number: US-2007106926-A1

Title: Viterbi decoding method and apparatus for high speed data transmissions

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
      This application claims priority under 35 U.S.C. § 119 from Korean Patent Application 10-2005-106057 filed on Nov. 7, 2005 in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference.  
     FIELD OF THE INVENTION  
      The present invention relates to a Viterbi decoding method and apparatus for high speed data transmissions. More particularly, the present invention relates to a Viterbi decoding method and apparatus for high speed data transmissions wherein branch metric is used with data inputted from a Viterbi decoder used in a communication system, and, when current state metric is used for addition, comparison, and selection, the selection operation is performed after simultaneous addition and comparison operations, so that a faster decoding processing speed is obtained.  
     BACKGROUND OF THE INVENTION  
      Generally, in a system that uses an air interface as a communication channel, the transmitter side encodes and transmits data through a convolutional encoder, and a receiver side corrects errors and decodes data using a Viterbi decoder, in order to overcome the errors caused by noise occurring during communications.  
      In exemplary embodiments of the present invention, discussions have been made on approaches of using the Viterbi decoder with input data and specifying branch metric, storing current state metric selected through addition and comparison of a specified result to and with an established value, and reducing the number of times a state metric RAM is accessed, and using the stored data as a previous state in subsequent additions, comparisons, and selections, thereby reducing an overall processing speed.  FIG. 1  is a block diagram for schematically showing a configuration of a conventional Viterbi decoder.  
      A conventional Viterbi decoder  100  has an input operation unit  110 , addition/comparison/selection unit  120 , and output unit  130 .  
      The input operation unit  110  receives the output data of a demodulator (not shown), calculates a branch metric, and outputs output data BM 0  to BM 3 .  
      The addition/comparison/selection unit  120  inputs and adds the output data BM 0  to BM 3  of the input operation unit  110  to a previous state metric (PSM) previously established, and forms current state metrics (CSM), selects and stores a smaller current state metric (CSM), and selects and outputs comparison information when outputting the value as a previous state metric (PSM) in a subsequent state.  
      The output unit  130  receives the comparison information of the addition/comparison/selection unit  120 , checks errors of received data, and decodes and outputs the data.  
      Further, the addition/comparison/selection unit  120  includes a first addition/comparison/selection block  122 , a second addition/comparison/selection block  124 , state metric storage unit  126 , and multiplexer  128 .  
      The first and second addition/comparison/selection blocks  122  and  124  respectively receive output data BM 2  and BM 3  of the input operation unit  110  and add the data to the previously established previous state metric PSM so as to create a current state metric (CSM), compare the current state metrics with each other, and select and output a smaller current state metric (CSM).  
      The state metric storage unit  126  receives and stores output data of the first and second addition/comparison/selection blocks  122  and  124 , and selectively outputs the stored output data to the inputs of the first and second addition/comparison/selection blocks  122  and  124  as previous state metrics.  
      Next, the multiplexer  128  receives and outputs the results of data comparisons from the first and second addition/comparison/selection blocks  122  and  124 , respectively, as comparison information.  
      In the Viterbi decoder  100  configured as above, the adders ADD 0  to ADD 3  of the first and second addition/comparison/selection blocks  122  and  124  respectively receive, add, and output a previous state metric (PSM) and the output data BM 0  to BM 3  of the input operation unit  110 . The comparators COMP 0  and COMP 1  that receive the outputted data respectively compare the output values of the adders ADD 0  and ADD 1  and the adders ADD 2  and ADD 3 , and simultaneously outputs to the selection units SELECT 0  and SELECT 1  and inputs to the multiplexer  128  the information of a smaller value of the output values.  
      The selection unit SELECT 0  then selects and outputs either the adder ADD 0  or the adder ADD 1  dependent on which current state metric CSM has a smaller output signal, and the selection unit SELECT 1  selects and outputs either the adder ADD 2  or the adder ADD 3  dependent on which current state metric CSM has a smaller output signal, according to the output signals of the comparison units COMP 0  and COMP 1 .  
      Next, the current state metrics selected by the selection units SELECT 0  and SELECT 1  are stored in the state metric RAM and, when subsequent data are inputted through the input operation unit  110 , the stored value is outputted to the adders ADD 0  to ADD 3  for additions, comparisons, selections, and storage as to the subsequent data in the same manner, the operations of which are repeated as many times as needed.  
      Accordingly, the conventional Viterbi decoder  100  has a slow decoding speed, since the addition, comparison, and selection procedures are sequentially processed as described above. Additionally, the conventional Viterbi decoder has an increased power consumption, since the number of times the state metric RAM is accessed is more than is needed since write and read operations to and from the state metric RAM are performed every time a state is calculated.  
     SUMMARY OF THE INVENTION  
      The present invention has been developed in order to address the above drawbacks and other problems associated with the conventional arrangement. An aspect of the present invention is to provide a Viterbi decoding method and apparatus for high speed data transmissions wherein branch metric is used with data inputted from a Viterbi decoder used in a communication system, and, when current state metric is used for addition, comparison, and selection, the selection operation is performed after the simultaneous addition and comparison operations, so that a faster decoding processing speed is obtained.  
      The foregoing and other aspects and advantages are substantially realized by providing a Viterbi decoding method, comprising performing branch metric calculations with input data, and outputting output data; simultaneously performing additions and comparisons of the output data by using a fed-back previous state metric; selecting a minimum value from a result of the simultaneous additions and comparisons; and checking errors of the inputted data by executing a trace-back algorithm and decoding the data.  
      In performing additions and comparisons, the additions are performed in a Carry Look-ahead Adder (CLA) by three bits, and the result is processed in a Carry SeLect Adder (CSLA)  
      The three-bit CLA is configured with a CLA 0  indicating that an LSB input is “0” and a CLA 1  indicating that the input is “1”, and the addition of three bits is carried out at the same time, and a result of which is selected by a multiplexer.  
      In performing additions and comparisons, the comparisons are performed based on subtractions with use of carry-save (CS) addition and comparing two input data through MSB of a result of the subtractions.  
      The foregoing and other objects and advantages are substantially realized by providing a Viterbi decoding apparatus comprising an input operation unit for performing branch metric calculations with input data, and outputting output data; an addition/comparison unit for simultaneously performing additions and comparisons of the output data by using a fed-back previous state metric; a selection unit for selecting a minimum value from a result of the simultaneous additions and comparisons; and an output unit for checking errors of the inputted data by executing a trace-back algorithm, and decoding the data.  
      The addition/comparison unit is constructed with adders and comparators connected in parallel, and the adders are performed in a CLA by three bits, and a result of which is processed in a CSLA.  
      The three-bit CLA is configured with a CLA 0  indicating that an LSB input is “0” and a CLA 1  indicating that the input is “1”, and the addition of three bits is carried out at the same time, and a result of which is selected by a multiplexer.  
      The comparators are constructed with CS adders. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The above aspects and features of the present invention will be more apparent by describing certain exemplary embodiments of the present invention with reference to the accompanying drawings, in which:  
       FIG. 1  is a block diagram for schematically showing a configuration of a conventional Viterbi decoder;  
       FIG. 2  is a block diagram for schematically showing a configuration of a Viterbi decoding apparatus according to an exemplary embodiment of the present invention;  
       FIG. 3  is a view for showing an internal configuration of an adder; and  
       FIG. 4  is a view for showing an internal configuration of each comparator of a comparison unit. 
    
    
     DETAILED DESCRIPTION OF THE EXEMPLARY EMBODIMENTS  
      Hereinafter, description will be made in detail on preferred exemplary embodiments of the present invention with reference to the accompanying drawings.  
      It is noted that like reference numerals are used to denote like parts or elements even though shown in different drawings in assigning the reference numerals to constituent parts or elements of each drawing.  
      For purposes of simplification, detailed description of well-known structures or functions will be avoided if it is understood that concrete description of such structures or functions is not necessary for understanding the present invention.  
       FIG. 2  is a block diagram for schematically showing a configuration of a Viterbi decoding apparatus according to an exemplary embodiment of the present invention.  
      The Viterbi decoding apparatus  200  according to an exemplary embodiment of the present invention has an addition unit  210  and a comparison unit  220  which are disposed in parallel, and is configured for the outputs of the addition unit  210  and the comparison unit  220  to be inputted into a selection unit  230  at the same time. Since the input operation unit  110  was described above, it is not shown in  FIG. 2 .  
      The addition unit  210  has a configuration having a first adder  212 , a second adder  214 , a third adder  216 , and a fourth adder  218 . The first adder  212  outputs a first sum value sum 0  for two inputs λ a,i (n−2) and γ a (n−2); the second adder  214  outputs a second sum value sum 1  for two inputs λ b,i (n−2) and γ b (n−2); the third adder  216  outputs a third sum value sum 2  for two inputs λ c,i (n−2) and γ c (n−2), and the fourth adder  218  outputs a fourth sum value sum 3  for two inputs λ d,i (n−2) and γ d (n−2).  
      The comparison unit  220  has a configuration having a first comparator (Substractor 0 )  221 , a second comparator  222 , a third comparator  223 , a fourth comparator  224 , a fifth comparator  225 , and a sixth comparator  226 .  
      In the exemplary embodiment of the present invention, the first comparator  221  outputs a first comparison value MSB 0  for four inputs λ a,i (n−2), γ a (n−2), λ b,i (n−2), and γ b (n−2); the second comparator  222  outputs a second comparison value MSB 1  for four inputs λ a,i (n−2), γ a (n−2), λ c,i (n−2), and γ c (n−2); the third comparator  223  outputs a third comparison value MSB 2  for four inputs λ a,i (n−2), γ a (n−2), λ d,j (n−2), and γ d (n−2); the fourth comparator  224  outputs a fourth comparison value MSB 3  for four inputs λ b,i (n−2), γ b (n−2), λ c,i (n−2), and γ c (n−2); the fifth comparator  225  outputs a fifth comparison value MSB 4  for four inputs λ b,i (n−2), γ b (n−2), λ d,i (n−2), and γ d (n−2), and the sixth comparator  226  outputs a sixth comparison value MSB 5  for four inputs λ c,i (n−2), γ c (n−2), λ d,i (n−2), and γ d (n−2).  
      The Viterbi decoding apparatus  200  according to the present invention may use offset binary numbers rather than redundant number representation.  
       FIG. 3  is a view for showing the internal configuration of an addition unit.  
      As shown in  FIG. 3 , the addition unit  210  according to the present invention processes input data by three bits at a time, using a (Carry Look-Ahead Adder) (CLA), and processes the result, using a Carry SeLect Adder (CSLA)).  
      In the present invention, each CLA is constructed with a CLA 0  indicating that the carry input of the LSB is “0” and a CLA 1  indicating that the carry input of the LSB is “1”.  
      Further, the addition of every three bits is processed at a time, and the result is selected by the multiplexers MUX 1  and MUX 2 . The MSB (carry out) of the addition result of the lower three bits is in charge of the controls of the multiplexers.  
      In  FIG. 3 , inputs a 0 , b 0 , a 1 , b 1 , a 2 , and b 2  are inputted into the CLA 0 , and c 0 , c 1 , and c 2  are outputted, and carries are applied to the multiplexer MUX 1  when carries are generated. Inputs a 3 , b 3 , a 4 , b 4 , a 5 , and b 5  are inputted into both the CLA 0  and the CLA 1 , and all the outputs and carries of the CLA 0  and the CLA 1  are inputted into the multiplexer MUX 1 . Multiplexer MUX 1  outputs c 5 , c 4 , and c 3 , and the carries are applied to the next multiplexer MUX 2 . Inputs a 6 , b 6 , a 7 , b 7 , a 8 , and b 8  are inputted into both the CLA 0  and the CLA 1 , and all the outputs and carries of the CLA 0  and the CLA 1  are inputted into the second multiplexer MUX 2 , the second multiplexer MUX 2  outputs c 6 , c 7 , and c 8  together with a carry.  
       FIG. 4  is a view for showing the internal configuration of each comparator in the comparison unit.  
      As shown in  FIG. 4 , the comparator according to the present invention performs comparisons through subtractions so as to operate in the same manner as an adder in a functional aspect, and uses a Carry-Saver (CS) adder for such a subtraction function.  
      In  FIG. 4 , if inputs λ a , γ a , and λ b  are inputted into a first CS adder  410 , the first CS adder  410  outputs a result as shown in Equation 1 at a point (a). 
 
( a )=λ a +γ a +(γλ a )  [Equation 1]
 
      Further, if the output of the first CS adder  410  and the input signal γ a  are inputted into a second CS adder  420 , the second CS adder  420  outputs a result as shown in Equation 2 at a point (b). 
 
( b )=λ a +γ a +(−λ b +1)+(−γ b )  [Equation 2]
 
      Further, if the output and the carry of the second CS adder  420  are inputted into a third CS adder  430 , the third CS adder  430  outputs a result as shown in Equation 3 at a point (c). 
 
( c )=λ a +γ a +(−λ b +1)+(−γ b +1)  [Equation 3]
 
      As described above, the values outputted through the addition unit  210  and the comparison unit  220  are inputted into the selection unit  230 . Accordingly, the selection unit  230  operates in the manner as shown Equation 4, and outputs a minimum value MSB. 
 
if (MSB0==0 &amp;&amp; MSB1==0 &amp;&amp; MSB2=0) 
 
 Yi ( n )=sum0; 
 
selected path=0; 
 
else if (MSB0==1 &amp;&amp; MSB3==0 &amp;&amp; MSB4==0) 
 
 Yi ( n )=sum1; 
 
selected path=1; 
 
else if (MSB1==1 &amp;&amp; MSB3==1 &amp;&amp; MSB5==0) 
 
 Yi ( n )=sum2; 
 
selected path=2; 
 
else 
 
 Yi ( n )=sum3; 
 
selected path=3;  [Equation 4]
 
      As explained above, the present invention carries out the decoding process at a high speed with the addition and comparison operations carried out simultaneously, thereby bringing out an effect capable of preventing the increase of power consumption.  
      The aforementioned is merely an illustrative description on the technical spirit of the present invention, and various changes and modifications can be made by those skilled in the art to which the present invention pertains without departing from the essential features of the present invention.  
      Accordingly, the disclosed exemplary embodiments of the present invention are not for limitation of the technical spirit of the present invention but for description thereon, so the scope of the technical spirit of the present invention is not limited by the exemplary embodiments.  
      The scope of the present invention should be construed by the appended claims, and all the technical spirit within the equivalency should be construed to be included in the scope of the present invention.