Abstract:
A branch metric duplication method substantially reduces interconnection delays. The branch metric duplication method is particularly useful to implement a high speed radix-4 Viterbi decoder targeted for FPGA applications.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    This invention relates generally to Viterbi decoders. More particularly, this invention relates to a branch metric unit duplication method to achieve high speed decoder field programmable gate array (FPGA) implementation. 2. Description of the Prior Art  
           [0003]    A Viterbi decoder performs an optimum decoding of convolutionally encoded digital sequences. It is widely used in digital communication systems with data rates ranging from few kbps in narrowband applications to several hundreds of Mbps in broadband applications like Wireless LAN.  
           [0004]    As shown in FIG. 1, a Viterbi decoder  100  is comprised of three units: a branch-metric computation unit (BMU)  102 , an add-compare select unit (ACSU)  104  and a survivor path memory unit (SMU)  106 . The input data is used in the BMU  102  to calculate the set of branch metrics for each new time step. These metrics are then fed to the ACSU  104  that accumulates the branch metrics recursively as path metrics according to the trellis determined by a convolutional encoder polynomial. The SMU  106  processes the decisions being made in the ACSU  104  and outputs an estimated path, with a latency of trace-back depth.  
           [0005]    It is clear that ACSU  104  and SMU  106  architectures depend only on the trellis and hence these two units are independent of the application for which a Viterbi decoder is being used. The application specific computations are done in the BMU  102  according to soft input definition; and the interpretation of the decoded path into data at the output of the SMU  106  is also dependent upon the output format definition. Since the application specific parts of a Viterbi decoder are mainly found at the input and output, the high speed architecture of ACSU  104  can be generally applicable.  
           [0006]    If a high speed Viterbi decoder needs to be implemented for broadband applications with greater than  100  Mbps data rates, the critical path of a Viterbi decoder must be minimized. By looking at the block diagram of a Viterbi decoder  100  in FIG. 1, it is obvious that the BMU  102  as well as the SMU  106  are purely feedforward and the throughput can easily be increased by massive pipelining. However, this does not hold for the ACSU  104 .  
           [0007]    One way to improve the throughput of ACSU  104  is to apply a look-ahead scheme (radix-4 architecture) to the trellis  200  as shown in FIG. 2. A radix-4 architecture achieves a double data rate without increasing the clock rate because a radix-4 architecture can run at the clock rates employed by a radix-2 architecture. The circuit complexity associated with a conventional radix-4 architecture is greater however, as can be seen with reference to FIG. 3 and FIG. 4, where a conventional radix-4 ACSU  400  basically requires 2-stage comparison circuits  401 ,  402  including 4 more adders and 2 more multiplexers than that required by a conventional radix-2 ACSU  300  shown in FIG. 3.  
           [0008]    Further, interconnection between BMU  102  and ACSU  104  cause longer routing delays because the ACSU circuit  104  takes more area and hence interconnections between the ACS cell  104  and BMU  102  as shown in FIG. 5 become complicated. Regarding a FPGA implementation, the ACSU  104  is expected to be fitted into several slices or logic cells; and hence, the routing delay gets even more dominant and comprises about 50% of the critical path delay.  
           [0009]    In view of the foregoing, it is both advantageous and desirable to provide a branch metric duplication method that substantially reduces interconnection delays in order to implement a high speed radix-4 Viterbi decoder targeted for FPGA applications.  
         SUMMARY OF THE INVENTION  
         [0010]    The present invention is directed to a branch metric duplication method that substantially reduces interconnection delays. The branch metric duplication method is particularly useful to implement a high speed radix-4 Viterbi decoder targeted for FPGA applications.  
           [0011]    According to one embodiment, a method of reducing interconnection delays associated with a Viterbi-decoder comprises the steps of providing a plurality of branch metric computation units (BMCUs) and at least one add-compare-select unit (ACSU) having a plurality of cells; connecting a first BMCU selected from the plurality of BMCUs to a first group of ACSU cells selected from the plurality of ACSU cells; and connecting a second BMCU selected from the plurality of BMCUs to a second group of ACSU cells selected from the plurality of ACSU cells.  
           [0012]    According to another embodiment, a high speed radix-4 Viterbi decoder comprises a field programmable gate array (FPGA) comprising a plurality of branch metric computation units (BMCUs) and at least one add-compare-select unit (ACSU) having a plurality of cells, wherein a first BMCU selected from the plurality of BMCUs is connected to a first group of ACSU cells selected from the plurality of ACSU cells, and a second BMCU selected from the plurality of BMCUs is connected to a second group of ACSU cells selected from the plurality of ACSU cells; and a survivor path memory unit (SPMU), wherein the plurality of BMCUs, the at least one ACSU, and the SPMU are configured in the FPGA to implement a radix-4 Viterbi decoder.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]    Other aspects and features of the present invention and many of the attendant advantages of the present invention will be readily appreciated as the same become better understood by reference to the following detailed description when considered in connection with the accompanying drawings wherein:  
         [0014]    [0014]FIG. 1 is a system block diagram illustrating a conventional Viterbi decoder;  
         [0015]    [0015]FIG. 2 is a diagram illustrating a radix-4 trellis for K=3,4 states;  
         [0016]    [0016]FIG. 3 is a circuit diagram illustrating a conventional radix-2 add-compare-select circuit;  
         [0017]    [0017]FIG. 4 is a circuit diagram illustrating a conventional radix-4 add-compare-select circuit;  
         [0018]    [0018]FIG. 5 is a block diagram illustrating application of BMC unit to an ACS unit; and  
         [0019]    [0019]FIG. 6 is a block diagram illustrating a technique for reducing interconnection delays between the BMC unit and the ACS unit shown in FIG. 5, according to one embodiment of the present invention. 
     
    
       [0020]    While the above-identified drawing figures set forth particular embodiments, other embodiments of the present invention are also contemplated, as noted in the discussion. In all cases, this disclosure presents illustrated embodiments of the present invention by way of representation and not limitation. Numerous other modifications and embodiments can be devised by those skilled in the art which fall within the scope and spirit of the principles of this invention.  
       DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0021]    Looking again at FIG. 5, a conventional architecture  500  comprises one branch metric computation (BMC) unit  102  and 64-state ACS unit  104  cells. If this architecture  500  is fitted into a FPGA, the interconnections between the BMC unit  102  and the 64 ACS unit cells  502  as well as the logic gates of 64 states are mapped into several slices. This undesirably causes long routing delays.  
         [0022]    [0022]FIG. 6 is a block diagram illustrating a technique  600  for reducing interconnection delays between the BMC unit  102  and the ACS unit  104  shown in FIG. 5, according to one embodiment of the present invention. Specifically, technique  600  reduces the interconnection delay between the branch metric computation unit  102  and 64-state ACS cells  502  by employing two identical branch metric computation logics  602 ( a ) and  602 ( b ) in place of the single BMCU  102  seen in FIG. 5.  
         [0023]    The present inventors employed synthesis and place and route techniques to discover that technique  600  desirably achieved improved (higher) speed (greater throughput). Table 1 below summarizes theses synthesis and place and route results applied to a Viterbi decoder implemented in a FPGA.  
                                 TABLE 1                           Synthesis Results for Viterbi Decoder Using FPGA                    Speed after   Logic usages (number       Circuit   Speed after synthesis   place &amp; route   of used slices)                   81.5 MHz   67.899 MHz   30%           90.0 MHz   79.526 MHz   31%                  
 
         [0024]    In summary explanation of the above, a branch metric unit duplication method  600  was shown to achieve FPGA implementation for a high speed radix-4 Viterbi decoder. Synthesis and place and route results verified the branch metric unit duplication method  600  improves radix-4 Viterbi decoder speed from 67.889 MHz to 73.926 MHz at the modest cost of only a small amount of hardware increase.  
         [0025]    In view of the above, it can be seen the present invention presents a significant advancement in the art of Viterbi decoders. Further, this invention has been described in considerable detail in order to provide those skilled in the FPGA art with the information needed to apply the novel principles and to construct and use such specialized components as are required.  
         [0026]    Further, in view of the foregoing descriptions, it should be apparent that the present invention represents a significant departure from the prior art in construction and operation. However, while particular embodiments of the present invention have been described herein in detail, it is to be understood that various alterations, modifications and substitutions can be made therein without departing in any way from the spirit and scope of the present invention, as defined in the claims which follow.