Abstract:
A device including a minimal trellis decoder is disclosed. The device can receive an encoded codeword, which the minimal trellis decoder efficiently decodes. In a specific implementation, the device can include a Bluetooth receiver that, in operation, receives an encoded codeword from a Bluetooth transmitter, which is decoded by the minimal trellis decoder.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to U.S. Provisional Application 60/797,956, entitled Multimedia Cell Platform, filed May 4, 2006, which is incorporated by reference. 
    
    
     BACKGROUND 
     In digital communication, transmission of information sometimes produces error. Techniques of reducing and monitoring error have been developed. Error can be monitored and sometimes corrected. One area that has developed has centered around Hamming codes, and particularly shortened Hamming codes. 
     Hamming codes introduce redundancy in data by adding information to existing data to identify and correct error following transmission of the data. For example, appending an error correction code to a unit of data and transmitting the resulting codeword can allow for higher tolerance to noise and error. 
     Typically, a transmitter encodes a data unit to produce what is sometimes referred to as a “codeword.” The transmitter then sends the codeword to a receiver. Typically, a receiver decodes the codeword to obtain the original data unit and the error correction code. A decoder in the receiver may include a trellis representation of a Hamming code. A trellis representation is a view of a convolutional or block code explained using a trellis diagram. 
     In drawing a trellis, sets of states are used to represent all possible points which can be assumed at successive stages by a state machine, which is used to encode source data. Before sending, data is encoded into a codeword from a limited number of possible codewords including error correction data. Only a specific set of codewords is permitted for transmission. Upon receipt, a receiver implementing a trellis decoder decodes the codewords and provides the data to a communications system. 
     Once a codeword has been properly received, a trellis search algorithm, such as the Viterbi algorithm or the Bahl, Cocke, Jelinek, Raviv (BCJR) algorithm, can be used to decode the codeword. Notably, there is a large number of computational steps required to perform Viterbi or other trellis decoding. The complexity of a decoder based on the Viterbi or other trellis search algorithms may increase in complexity based on the size of the trellis structure corresponding to the decoder. The number of computational steps required to perform Viterbi or other trellis search decoding is related to the size of the trellis structure used to implement the decoder. 
     SUMMARY 
     The following embodiments and aspects thereof are described and illustrated in conjunction with systems, tools, and methods that are meant to be exemplary and illustrative, not limiting in scope. In various embodiments, one or more of the above-described problems have been reduced or eliminated, while other embodiments are directed to other improvements. Advantageously, this technique can decrease complexity while reducing power consumption. It may even facilitate a reduction in die size. 
     The proposed decoding technique applies to any system that uses a shortened Hamming (15, 10) block code. This code is used, for example, in Bluetooth radios, where reduced decoding complexity is extremely important due to the need for low power. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the inventions are illustrated in the figures. However, the embodiments and figures are illustrative rather than limiting; they provide examples of the inventions. 
         FIG. 1  depicts a prior art traditional trellis representation for a shortened Hamming (15, 10) code. 
         FIG. 2  depicts an example of a minimal trellis representation of a shortened (15, 10) Hamming code. 
         FIG. 3  depicts a diagram of an example of several states of a trellis having three different branching structures. 
         FIG. 4  depicts an example of a conceptual diagram illustrating reorganization of a codeword. 
         FIG. 5  depicts a graphical diagram of an example of an arbitrary path through the minimal trellis which might be selected by the Viterbi or other trellis search algorithm when decoding a codeword. 
         FIG. 6  depicts a decoder including a mapping engine and a minimal trellis implemented in a computer readable medium. 
         FIG. 7  depicts a flowchart of an example of a method for obtaining information bits from an encoded codeword. 
         FIG. 8  depicts an example of a system including a Bluetooth receiver with a minimal trellis decoder. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the following description, several specific details are presented to provide a thorough understanding of 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 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. 
       FIG. 1  depicts a prior art example of a traditional trellis representation  100 , which is viewed for illustrative purposes as a convolutional code for a shortened (15, 10) Hamming code. The traditional trellis representation  100  includes a plurality of stages  102  (in the example of  FIG. 1 , there are 15 stages). The stages  102  may be categorized based upon their position in the trellis. In the example of  FIG. 1 , the first five of the states  102  may be referred to as initial stages  104 - 1  to  104 - 5  (referred to collectively as initial stages  104 ), the second five of the stages  102  may be referred to as intermediate stages  106 - 1  to  106 - 5  (referred to collectively as intermediate stages  106 ), and the third five of the stages  102  may be referred to as final stages  108 - 1  to  108 - 5  (referred to collectively as final stages  108 ). 
     In the example of  FIG. 1 , the traditional trellis representation  100  includes nodes  110  that are associated with states of the traditional trellis representation  100 . The first of the nodes  110  may be referred to as an initial node  112  (which may be referred to as an initial node set, where the set includes a single node), the second node set of the nodes  110  may be referred to as one-hop nodes  114  because there is one branch from the initial node to the one-hop nodes, the third set of the nodes  110  may be referred to as two-hop nodes  116 , and so forth to the final node  118  (which may be referred to as a final node set, where the set includes a single node). In the example of  FIG. 1 , the initial node  112  may be referred to in the alternative as a zero-hop node because zero hops are needed in the traditional trellis representation  100  to reach the initial node  112 ; and the final node  118  may be referred to in the alternative as a 15-hope node because there are  15  stages in the traditional trellis representation  100 . 
     It may be noted that the initial node  112  need not be treated as part of the initial stages  104  nodes (at least in part because it does not have one input branch like the one-hop to five-hop node sets). For similar reasons (i.e., the 10-hop nodes have different characteristics from the six- to nine-hop nodes), the 10-hop nodes may be treated as part of the final stages  108  nodes, rather than the intermediate stages  106  nodes, though at times it will be convenient to refer to the 10-hop nodes as part of the intermediate stages  106  nodes. For similar reasons (i.e., the final node  118  has no output branches), the final node  118  need not be treated as part of the final stages  108 . 
     In the example of  FIG. 1 , the nodes  110  are coupled via branches  120 . Initial stages  104  nodes include two initial stage output branches  122 - 1  and  122 - 2  (referred to collectively as the initial stage output branches  122 ). Initial stages  104  nodes have a single input branch (except for the initial node  112 ). Since each node of the initial stages has one input and two outputs, each successive stage of the traditional trellis representation  100  has twice as many nodes as the last, or, more generally, 2 i  nodes, where i is the number of hops to get to the stage. Thus, after initial stage  104 - 5 , there are 32 nodes in the five-hop node set. 
     In the example of  FIG. 1 , the intermediate stages  106  nodes include two intermediate stage output branches  124 - 1  and  124 - 2  (referred to collectively as the intermediate stage output branches  124 ). Intermediate stages  106  nodes also have two input branches. Since each node of the intermediate stages has two inputs and two outputs, each successive intermediate stage of the traditional trellis representation  100  has the same number of stages as the previous stage. 
     In the example of  FIG. 1 , the final stages  108  nodes include one final stage output branch  126 . Final stages  108  nodes also have two input branches. Since there are fewer output branches than input branches, a final stage output branch  128  is provided as input to a same node as the final stage output branch  126 , and each successive final stage of the traditional trellis representation  100  has fewer stages than the previous stage. In general, there are 2 n−i  nodes, where n is the total number of stages and i is the number of hops to get to the stage. Thus, after final stage  108 - 5 , which is a 15 th -hop stage, there is one node (i.e., the final node  118 ) in the final node set. 
     As should be apparent from the example of  FIG. 1 , complexity of the traditional trellis representation  100  is determined by the number of branches and states in the trellis. In general, the greater the number of states and branches, the greater the complexity of a corresponding decoder. 
     As a rule, in the traditional trellis representation  100 , a set of i-hop nodes is an initial stage set of nodes if the set of i+1-hop nodes is a larger set; the set of i-hop nodes is an intermediate stage set of nodes if a set of i+1-hop nodes is an equal set; the set of i-hop nodes is a final stage set of nodes if a set of i+1-hop nodes is a smaller set. In general, such a rule cannot be rigidly applied to a minimal trellis representation, such as depicted later by way of example but not limitation in  FIG. 2 . 
     An (N, K) block code with codewords of length N for K information bits can be represented as a punctured convolutional code and decoded using a time-invariant trellis with N sections and 2 N−K  states. The shortened Hamming (15, 10) code used in Bluetooth is a systematic code, so the first K=10 bits of a codeword are the information bits, and the remaining N−K=5 bits of a codeword are parity bits generated by modulo-2 addition of different combinations of the information bits. The codebook C has 2 10 =1024 codewords. The generator polynomial for the shortened Hamming code (15,10) is
 
 g ( D )=( D+ 1)( D   4   +D+ 1)= D   5   +D   4   +D   2 +1.
 
     The generator matrix can be found from the generator polynomial 
             G   =       [         1       0       0       0       0       0       0       0       0       0       1       1       0       1       0           0       1       0       0       0       0       0       0       0       0       0       1       1       0       1           0       0       1       0       0       0       0       0       0       0       1       1       1       0       0           0       0       0       1       0       0       0       0       0       0       0       1       1       1       0           0       0       0       0       1       0       0       0       0       0       0       0       1       1       1           0       0       0       0       0       1       0       0       0       0       1       1       0       0       1           0       0       0       0       0       0       1       0       0       0       1       0       1       1       0           0       0       0       0       0       0       0       1       0       0       0       1       0       1       1           0       0       0       0       0       0       0       0       1       0       1       1       1       1       1           0       0       0       0       0       0       0       0       0       1       1       0       1       0       1         ]     .           
This code has a minimum Hamming distance of 4.
 
     The trellis for the shortened Hamming (15, 10) code viewed as a convolutional code has 32 states per section (disregarding the initial and the termination sections) and its typical representation is shown in  FIG. 1 . In the example of  FIG. 1 , the black dots are trellis states, also referred to as nodes herein, the dashed line branches are for output bit  0 , and the solid line branches are for output bit  1 . For a (15,10) systematic code, the first 10 output bits of the codeword (over Stages  1 - 10 ) correspond to the 10 input bits, and the last 5 output bits of the codeword (over Stages  11 - 15 ) are the parity bits. There are 1024 paths through the trellis, corresponding to the 1024 codewords in the codebook C, and it is easy to map a trellis path to a codeword based on the branch line style (e.g., solid or dashed). The codeword in turn is easy to map to the information bits since it is systematic (hence the first 10 bits of the codeword are the information bits). 
     Viterbi decoding can be implemented based on a trellis representation for a code by eliminating codewords associated with all paths into each trellis state except the path with the maximum likelihood metric. The complexity of the decoder can be measured in the number of solid line branches (which correspond to additions in computing the metric) and the number of states that have two entering branches (which correspond to comparisons to decide which has the larger metric). The trellis in  FIG. 1  has a maximum of 32 states per section, 253 total states, and 444 total branches, as summarized in Table 1. The number of additions is half the number of branches. The number of additions and the number of comparisons are also summarized as the two last rows in Table 1, assuming that the search starts from the end of the trellis. 
     
       
         
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Decoder complexity for trellis of FIG. 1. 
               
             
          
           
               
                 Section 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
                 Tot. 
               
               
                   
               
             
          
           
               
                 # States 
                 1 
                 2 
                 4 
                 8 
                 16 
                 32 
                 32 
                 32 
                 32 
                 32 
                 32 
                 16 
                 8 
                 4 
                 2 
                 253 
               
               
                 # Branches 
                 2 
                 4 
                 8 
                 16 
                 32 
                 64 
                 64 
                 64 
                 64 
                 64 
                 32 
                 16 
                 8 
                 4 
                 2 
                 444 
               
               
                 # Adds. 
                 1 
                 2 
                 4 
                 8 
                 16 
                 32 
                 32 
                 32 
                 32 
                 32 
                 16 
                 8 
                 4 
                 2 
                 1 
                 222 
               
               
                 # Comp. 
                 1 
                 2 
                 4 
                 8 
                 16 
                 32 
                 32 
                 32 
                 32 
                 32 
                 0 
                 0 
                 0 
                 0 
                 0 
                 191 
               
               
                   
               
             
          
         
       
     
     The traditional trellis representation shown in  FIG. 1  for the shortened Hamming (15, 10) code is straightforward to obtain for any linear code as it follows directly from sequential operations on the information bits. However, there may be other trellis representations for a given code. In particular, a minimal trellis representation of a code is a representation with no redundant trellis states. It is known that such a minimal trellis representation exists for all linear codes. 
       FIG. 2  depicts an example of a minimal trellis representation  200  of a shortened Hamming (15, 10) code. The minimal trellis representation includes a plurality of stages  202  (in the example of  FIG. 2 , there are 15 stages). The stages  202  may be categorized based upon their position in the trellis. In the example of  FIG. 2 , the first four of the states  202  may be referred to as initial stages  204 - 1  to  204 - 4  (referred to collectively as initial stages  204 ); the 5 th , 6 th , 9 th , and 10 th  of the stages  202  may be referred to as intermediate stages  206 - 1  to  206 - 4  (referred to collectively as intermediate stages  206 ); the 7 th  and 8 th  of the stages  202  may be respectively referred to as pre-median stage  207 - 1  and post-median stage  207 - 2  (referred to collectively as median stages  207 ); the 11 th , 13 th , 14 th , and 15 th  of the stages  202  may be referred to as final stages  208 - 1  to  208 - 4  (referred to collectively as the final stages  208 ); the 12th of the stages  202  may be referred to as a staggered final stage  209 . In some cases, it may be convenient to refer to the median stages  207  as one of the “intermediate stages” and the staggered final stage  209  as one of the “final stages.” 
     In an illustrative embodiment, the number of initial stages is reduced by one. This is associated with a corresponding decrease in the size of the largest node sets to 16, rather than 32 as would be the case for a traditional trellis. The number of intermediate stages (assuming median stages are included) is increased by one. 
     The complexity of the minimal trellis representation  200  is associated with the number of branches and states in the trellis. Although the complexity is reduced in the minimal trellis relative to a traditional trellis (thereby tending to reduce the complexity of a corresponding decoder), the behavior at various nodes is more variable. For example, the intermediate nodes include median nodes, as previously mentioned, and the final nodes include staggered final stage nodes, which have a different number of branches into and/or out of the node than, respectively, the other intermediate or final nodes. 
     As in  FIG. 1 , in the example of  FIG. 2 , the outputs may be associated with a line style. Dashed line branches are for output bit  0 , solid line branches are for output bit  1 , and black dots represent the different trellis states. As with the traditional trellis, there are 1024 paths through the minimal trellis, each corresponding to a codeword in the codebook C*. The mapping of minimal trellis paths to codewords is also straightforward based on the branch line style. The codebooks C and C* both correspond to matrices with 1024 rows (corresponding to the number of codewords) and 15 columns (corresponding to the number of bits in each codeword). There exists a unique permutation of the columns of C that results in the minimal trellis codebook C*. Finding this permutation through an exhaustive search is computationally very complex since it entails checking all permutations to determine which results in the correct mapping between C and C*. Because of the complexity and the lack of other methods for determining the permutation associated with the minimal trellis, this permutation is unknown for most classes of codes, including most Hamming codes and shortened Hamming codes. 
     For the shortened Hamming (15, 10) code, we have found the permutation π that maps the codebook C to C* or, equivalently, maps the order of codeword bits in C to the order of the codeword bits in C*. This permutation of the 15 codeword bits r=[r 1 ,r 2 ,r 3 ,r 4 ,r 5 ,r 6 ,r 7 ,r 8 ,r 9 ,r 10 ,r 11 ,r 12 ,r 13 ,r 14 ,r 15 ] corresponding to the minimal trellis is given by r π =π(r)=[r 1 ,r 7 ,r 9 ,r 3 ,r 10 ,r 6 ,r 11 ,r 4 ,r 5 ,r 8 ,r 14 ,r 15 ,r 12 ,r 13 ,r 2 ], 
     The permutation is used to significantly decrease the complexity of the optimal decoder. Specifically, soft or hard decoding of the shortened Hamming (15,10) code can be performed by first permuting the received matched filter outputs s≈r according to the permutation π, where s is the received codeword corresponding to the transmitted codeword r, and can be based on either hard or soft decisions of the matched filter output. Next the resulting vector s π =π(s) is fed to the Viterbi (or other trellis search) decoder (operating on soft or hard inputs) corresponding to the minimal trellis in  FIG. 2  to obtain an estimate ŕ π  of the codeword corresponding to s π . Finally, the inverse permutation π −1  is applied to the estimated codeword ŕ π  to obtain the estimate of the received codeword ŕ=π −1 (ŕ π ). Since this is a systematic code, the first 10 bits of ŕ correspond to the estimate of the 10 information bits in the received codeword s. The algorithm of this decoding process for each transmitted codeword is shown in  FIG. 6 . 
     The number of additions and comparisons using the minimal trellis operating on the permutation s π  is reported in the two last rows of Table 2. The decoders based on the full trellis and the decoder based on the minimal trellis may or may not have identical performance. By comparing Table 1 and Table 2 it is clear that the decoder based on the minimal trellis has 47% fewer additions and 50% fewer comparisons. 
     
       
         
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Decoder complexity for the minimal trellis of FIG. 2 
               
             
          
           
               
                 Section 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
                 Tot. 
               
               
                   
               
             
          
           
               
                 # States 
                 1 
                 2 
                 4 
                 8 
                 16 
                 16 
                 16 
                 8 
                 16 
                 16 
                 16 
                 8 
                 8 
                 4 
                 2 
                 141 
               
               
                 # Branches 
                 2 
                 4 
                 8 
                 16 
                 32 
                 32 
                 16 
                 16 
                 32 
                 32 
                 16 
                 16 
                 8 
                 4 
                 2 
                 236 
               
               
                 # Adds. 
                 1 
                 2 
                 4 
                 8 
                 16 
                 16 
                 8 
                 8 
                 16 
                 16 
                 8 
                 8 
                 4 
                 2 
                 1 
                 118 
               
               
                 # Comp. 
                 1 
                 2 
                 4 
                 8 
                 16 
                 16 
                 0 
                 8 
                 16 
                 16 
                 0 
                 8 
                 0 
                 0 
                 0 
                 95 
               
               
                   
               
             
          
         
       
     
       FIGS. 3A to 3C  depict examples of nodes in a trellis representation. In the example of  FIG. 3A , a node  300 A has one input branch and two output branches. The node  300 A could be incorporated into an initial stage node of the traditional trellis representation  100  ( FIG. 1 ) or the minimal trellis representation  200  ( FIG. 2 ). In addition, the node  300 A could be incorporated into a median stage node of the minimal trellis representation  200 . 
     In the example of  FIG. 3B , a node  300 B has two input branches and two output branches. The node  300 B could be incorporated into an intermediate stage node of the traditional trellis representation  100  or the minimal trellis representation  200 . In addition, the node  300 B could be incorporated into a staggered final stage node of the minimal trellis representation  200 . 
     In the example of  FIG. 3C , a node  300 C has two input branches and one output branch. The node  300 C could be incorporated into a final stage node of the traditional trellis representation  100  or the minimal trellis representation  200 . In addition, the node  300 C could be incorporated into a median stage node of the minimal trellis representation  200 . 
       FIG. 4  depicts an example of a conceptual diagram  400  illustrating reorganization of a codeword. The diagram  400  includes a codeword  402 , an array of bit positions  404  of the codeword  402 , a mapping function  406 , an array of mapped bit positions  408 , and reorganizing indicators  410 . In the example of  FIG. 4 , the codeword  402  has 15 associated bit positions, depicted in the array of bit positions  404  as r 1  to r 15 . The mapping function  406  maps r to r π  as indicated in the example using the reorganizing indicators  410 . The mapping function may be represented as: π(r)=π([r 1 ,r 2 ,r 3 ,r 4 ,r 5 ,r 6 ,r 7 ,r 8 ,r 9 ,r 10 ,r 11 ,r 12 ,r 13 ,r 14 ,r 15 ])=[r 1 ,r 7 ,r 9 ,r 3 ,r 10 ,r 6 ,r 11 ,r 4 ,r 5 ,r 8 ,r 14 ,r 15 ,r 12 ,r 13 ,r 2 ]=r π . 
     In a non-limiting embodiment, the mapping function  406  may be implemented in a computer readable medium such that a mapping engine could reorganize bits of a codeword for decoding by a minimal trellis as depicted in the diagram  400 . The mapping function corresponds to the minimal trellis, and reorganizes codewords received that could be decoded by a traditional trellis. 
       FIG. 5 . depicts a graphical diagram  500  of an example of an arbitrary path through a minimal trellis which might be selected by a Viterbi or other trellis search algorithm when decoding a codeword. The diagram  500  includes mapping function  502 , codeword  504 , and path  506 . In the example of  FIG. 5 , mapping function  502  reorganizes the codeword  504 , and a maximum likelihood path can be traced through the minimal trellis. 
       FIG. 6  depicts a decoder  600  including a mapping engine and a minimal trellis implemented in a computer readable medium. The decoder  600  includes a mapping engine  602  and logic implementing a minimal trellis decoder  604 . In the example of  FIG. 6  the mapping engine  602  passes an encoded codeword through the logic implementing the minimal trellis search  604  to yield the codeword associated with the maximum likelihood path to which the inverse map π −1  is applied to obtain a decoded codeword. It may be noted that the inverse map π −1  is a part of the mapping engine  602  (i.e., the inverse representation of the function π that is implemented in a computer-readable medium in the mapping engine  602 ). A truncator  606  truncates the codeword. Since the decoded codeword is from a shortened Hamming (15, 10) code, truncating the codeword to the first 10 bits yields the information bits associated with the codeword. 
       FIG. 7  depicts a flowchart  700  of an example of a method for obtaining a information bits from an encoded codeword. In the example of  FIG. 7 , the flowchart  700  starts at module  702  where a hard or soft estimate of the codeword is found from the demodulated received signal. In the example of  FIG. 7 , the flowchart  700  continues to module  704  where the codeword is permuted by a permutation π associated with the minimal trellis representation of a shortened Hamming (15, 10) code. In the example of  FIG. 7 , the flowchart  700  continues to module  706  where decoding of the minimal trellis is applied to s π =π(s), where s is the received codeword, to get the permuted codeword estimate ŕ π . In the example of  FIG. 7 , the flowchart  700  continues to module  708  where the inverse permutation is applied to obtain the codeword estimate ŕ=π −1 (ŕ π ). In the example of  FIG. 7 , the flowchart  700  ends at module  710  with using the first 10 bits of ŕ as the estimate of the transmitted information bits. 
       FIG. 8  depicts an example of a system  800  including a Bluetooth receiver with a minimal trellis decoder. The system  800  includes a transmitter  802 , a Bluetooth receiver  804 , and a minimal trellis decoder  806  implemented on the Bluetooth receiver  804 . These devices function in accordance with techniques described previously. 
     While this invention has been described in terms of certain embodiments, it will be appreciated by those skilled in the art that certain modifications, permutations and equivalents thereof are within the inventive scope of the present invention. It is therefore intended that the following appended claims include all such modifications, permutations and equivalents as fall within the true spirit and scope of the present invention; the invention is limited only by the claims.