Abstract:
A prediction device and method for use in a Viterbi decoder is provided. The prediction device is applicable to a communication system with low bit error rate for reducing the count of accessing path memories, thereby lowering the power consumption of the system. The prediction device needs not activate the traceback modules when making a successful prediction. In other words, no access to the path memories is required. The predicted bits decoded and outputted by the decode bit registers are the decoded bits from the Viterbi decoder. Therefore, the prediction device saves much traceback works and power consumption for decoding.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention generally relates to a Viterbi decoder, and more specifically to a prediction device applicable in a Viterbi decode, and a method of forming the same.  
       BACKGROUND OF THE INVENTION  
       [0002]     A Viterbi decoder can be used in convolutional decoding, and is widely used in communication systems. The Viterbi decoder employs the method of searching for the maximum likelihood sequence and calculating the minimum path metric to accomplish the error correction. The recent wireless communication products all utilize the Viterbi decoder. However, without the external power source, the wireless communication products can only be sued for a limited duration as the power consumption is relatively high for the battery-powered products. Therefore, the criterion of low power consumption is important for the design of wireless communication products.  
         [0003]     The Viterbi decoder is the module that consumes much power in the wireless communication products. The conventional Viterbi decoder uses the following two approaches: register exchange approach and traceback approach.  
         [0004]      FIG. 1  shows the register exchange approach used in a conventional Viterbi decoder. As shown in  FIG. 1 , this approach stores the decoded bits of the survivor path of the current state into the register when an input signal arrives. The subsequent arrival of an input signal requires the duplication of previously decoded bits and writing the current decoded bits into the register. Therefore, the bits stored in the register will increases as the input signal increases. The register exchange approach eliminates the time and the power consumption of the traceback because the value stored in the register is the decoded bit sequence when the last input signal arrives. However, the duplication of the decoded bits of the previous stage to the next stage requires high power consumption and a large memory area; therefore, this approach can only be used in low complexity and high throughput systems.  
         [0005]      FIG. 2  shows the traceback approach of a conventional Viterbi decoder. As shown in  FIG. 2 , the traceback approach records the survivor branch of each state. For the Viterbi decoder with a total of four states, it requires two bits to record the survivor branch of the state and stores into the path memory. It can even use only one bit to record whether it is the upper branch or the lower branch. On tracebacking, by reading the path memory, with table look-up, the decoded bits can be obtained. Because this approach requires less power and smaller memory area, the traceback approach is suitable for high complexity systems.  
         [0006]      FIG. 3  shows a conventional three-pointer even method of memory management. The memory management method is applicable to the implementation of the traceback approach. By dividing the memory into a plurality of memory blocks, this method allows the parallel execution of the reading and writing to the memory. However, this method has an utilization rate of 4/6 for the memory; that is, four out of the allocated six blocks must be in use simultaneously. As the memory access uses about 80% of the power consumption, it is important to reduce the memory access and shut down the power to the memory block when the block is not in use so that the overall power consumption can be reduced.  
         [0007]     The conventional Viterbi decoder utilizes path memory to store each stage and the survivor branch of each stage. The tracebacking starts when the depth of the stored stages reaches about 5-6 times of the constraint length. During the traceback, the state of last stage having the minimum path metric is first found, and then the survivor path in the path memory is read to compute the state of the previous stage in the survivor path. This process must be done stage by stage, and the path memory must be accessed in each stage. Until tracebacking to the end of the survivor path, the decoded bits can be obtained. Because the number of memory accesses is large, the power consumption of this method is also large.  
         [0008]      FIG. 4  shows the relationship between the bit error rate (BER) and the path overlapping. A conventional prediction method utilizes the relationship between the BER and the path overlapping. When the input signal of the Viterbi decoder has a BER less than 3.7×1 0 −2 , the probability of the overlapping of the traceback path and the survivor path in the first three stages is higher than 97%. There are two important issues in this relationship. First, in a low BER system, the probability that the previous traceback path overlaps the current traceback path is high. If the information of the previous traceback path can be stored, the remaining tracebacking can be saved when the paths overlap. This also saves the power used in path memory access. Second, the survivor branch is recorded whenever an input signal arrives. If each stage computes the state of the minimum path metric, and determines the legitimacy of the state in the survivor path based on whether a connection exists between this state and the state of the minimum path metric of the previous stage, under the low BER condition, there will be a high probability that the survivor path will consist of the states of the minimum path metric of each stage.  
         [0009]     In this conventional prediction method, six corresponding state buffers are used in addition to the six path memories of a conventional Viterbi decoder. The state buffers record the state sequence of the previous traceback path and the most likely correct state sequence predicted by the prediction mechanism. When the predicted minimum states are connected, the state of the minimum path metric in the previous stage is recorded in the state buffer. During the tracebacking, if the traceback path overlaps the path in the state buffer, the connected state stored in the state buffer can be directly used to obtain the decoded bits. Thus, no further path memory access is required for the decoding. When the channel condition is good, that is, the path prediction mechanism is correct, 75% of memory access is saved in comparison to the traceback approach of the conventional Viterbi decoder. The power consumption is greatly reduced.  
         [0010]     Take the structure of the conventional three-pointer even method as example. There are four memory blocks operating simultaneously in the Viterbi decoder using a traceback approach. The conventional prediction method, when the path prediction mechanism is completely correct, writes the state of the minimum path metric of the previous stage into only one memory block. When the channel condition is good, that is, the path prediction mechanism is correct, it still requires to use the tracebacking to observe the connected relationship to obtain the decoded bits.  
         [0011]     For wireless communication products, the power consumption criterion is more restrictive because of the mobility. Although the traceback approach uses less power and less memory area than the register exchange approach, and is already widely used, it is still a challenge to further lower the power consumption.  
       SUMMARY OF THE INVENTION  
       [0012]     The present invention has been made to overcome the aforementioned drawback of conventional Viterbi decoder. The primary object of the present invention is to provide a prediction device applicable to the Viterbi decoder using the traceback approach for reducing the count of memory accesses and lowering the power consumption in a low BER system. The Viterbi decoder includes a path computing module, a path metric comparison module, a plurality of path memories, a traceback module, and a storage control module. In accordance with the present invention, the prediction device comprises a prediction module and a plurality of decoded bit storages.  
         [0013]     Based on the following: (1) a prediction activation signal from the storage control module, (2) a path source of each state in the current stage from the path computing module, (3) the state of the minimum path metric of the current stage from the path metric comparison module and (4) the state of the minimum path metric of the previous stage stored in the prediction module, the prediction module determines whether the state of the minimum path metric of the previous stage is connected to the state of the minimum path metric of the current stage, stores the state of the minimum path metric of the current stage, generates at least a decoded bit, and outputs a prediction success signal to the storage control module.  
         [0014]     Each of the plurality of decoded bit storages corresponds to a path memory, and stores at least a decoded bit outputted by prediction module or by the traceback module sequentially. A signal is arranged by the storage control module to be outputted to a decoded bit storage at a preset output time, and all the decoded bits stored in this decoded bit storage are outputted.  
         [0015]     Another object of the present invention is to provide a prediction method applicable to the aforementioned Viterbi decoder, where the storage control module of the Viterbi decoder includes a plurality of counters, and each counter corresponds to a decoded bit storage. The prediction method comprises the following steps of: (a) using a prediction module to determine, based on a plurality of parameters from the Viterbi decoder and a state of the minimum path metric of the previous stage stored in the prediction module, whether the state of the minimum path metric of the current stage being connected to the state of the minimum path metric of the previous stage; if not, stopping the prediction method until a preset activation condition being met and returning to step (a); (b) generating at least a decoded bit of the current stage, storing sequentially the decoded bit to one of the plurality of decoded bit storage, and adjusting the counter corresponding to the decoded bit storage being currently processed; (c) using a traceback mechanism to determine whether to directly output all the decoded bits in one of the decoded bit storage at a preset output time; and (d) the storage control module transmitting a decoded bit signal to the decoded bit storage corresponding to the last path memory being already traced-back, and the decoded bit storage outputting all decoded bits stored in it.  
         [0016]     During writing to the path memory of the Viterbi decoder, the prediction device of the present invention records the decoded bits when the predicted minimum states are connected. During the tracebacking, if the state of the current stage equals to the combination of the decoded bits of the previous several stages, it means the paths are overlapping. Thus, no further path memory access is required for the decoding, and the decoded bits can be directly outputted. When the channel condition is good, that is, the path prediction mechanism is correct, 75% of memory access is saved in comparison to the traceback approach of he conventional Viterbi decoder. The power consumption is greatly reduced.  
         [0017]     The foregoing and other objects, features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]      FIG. 1  shows a schematic view of a register exchange approach of a conventional Viterbi decoder.  
         [0019]      FIG. 2  shows a schematic view of a traceback approach of a conventional Viterbi decoder.  
         [0020]      FIG. 3  shows a three-pointer even method for memory management.  
         [0021]      FIG. 4  shows the relation between bit error rate (BER) and path overlapping.  
         [0022]      FIG. 5A  shows a schematic view of a prediction device of the present invention.  
         [0023]      FIG. 5B  shows a structure diagram of the prediction device of the present invention applied in a Viterbi decoder.  
         [0024]      FIG. 6  shows the relation between the decoded bit storage and the path memory.  
         [0025]      FIG. 7A  shows a flowchart of the prediction method of the present invention applied in a Viterbi decoder in  FIG. 6B .  
         [0026]      FIG. 7B  shows a flowchart for operating the prediction and traceback mechanism according to the present invention.  
         [0027]      FIG. 8  shows the simulation results of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0028]      FIG. 5A  shows a schematic view of a prediction device of the present invention and  FIG. 5B  shows a structure diagram of the prediction device of the present invention applied in a Viterbi decoder.  
         [0029]     As shown in  FIG. 5A  and  FIG. 5B , a prediction device  500  of the present invention is applied in a Viterbi decoder  520 . Prediction device  500  comprises a prediction module  501  and a plurality of decoded bit storages  511 - 51 N.  
         [0030]     Viterbi decoder  520  comprises a path computing module  521 , a path metric recording module  522 , a path metric comparison module  523 , a plurality of path memories  541 - 54 N, a traceback module  524 , and a storage control module  525 .  
         [0031]     Path computing module  521  is for computing the path metric of each state. By adding the tallied path metric of the previous stage to that of the survivor branch of each state, the current path metric can be obtained. Path metric recording module  522  is for recording the path metric of all the states and providing to path metric comparison module  523  for comparison. Path metric comparison module  523  compares the path metric of all the states, and finds the minimum as the starting point for traceback path. Storage control module  525  is for power management of the memories and the activation control of its peripheral modules.  
         [0032]     As shown in  FIG. 5B , based on an activation signal to the prediction mechanism signal outputted by storage control module  525 , the path source of all the states of the current stage outputted by path computing module  521 , the state of the minimum path metric of the current stage outputted by path metric comparison module  523 , and the state of the minimum path metric of the previous stage stored in prediction module  501 , prediction module  501  determines whether the state of the minimum path metric of the previous stage is connected to the state of the minimum path metric of the current stage. If so, the decoded bits of the current stage will be stored in decoded bit storages  511 - 51 N, the state of the minimum path metric of the current stage is also stored, and a prediction success signal is sent to storage control module  525 . Otherwise, the prediction is terminated until the current path memory is full. When the writing to the next path memory starts, the prediction mechanism is re-activated.  
         [0033]     Each decoded bit storage  51 N corresponds to a path memory  54 N, and sequentially stores the decoded bits outputted by prediction module  501  or the decoded bits outputted by traceback module  524 . A signal for outputting decoded bits is transmitted at a preset output time by storage control module  525  to a decoded bit storage  51 N to output all the decoded bits stored in this decoded bit storage  51 N.  
         [0034]      FIG. 6  gives an example to show the relation between the decoded bit storage and the path memory. In the example, a radix-4 design is employed. Although the hardware of the radix-4 design is twice complex as that of a radix-2 design, the processing speed is also twice as fast. Under the same data processing speed circumstances, the radix-4 design operates at a lower frequency and consumes less power. The truncation length of the present design is 64 bits.  
         [0035]     As shown in  FIG. 6 , the present design includes six path memories and six decoded bit storages, and one path memory corresponds to a decoded bit storage. The present design uses single port RAM as the path memory, each having the size of 128×16 bits. The path memory is divided into 16 stages, with each stage having 64 states. Each stage records a path source of each state, and each state uses two bits to store the survivor branch. The size of each decoded bit storage is 2×16 bits, and each stage stores two decoded bits. Traceback module  524  includes two traceback sub-modules  524   a ,  524   b , and a traceback and output sub-module  524   c  for tracebacking the maximum possible path. Storage control module  525  at least comprises six counters  531 - 536 , corresponding to six decoded bit storages  511 - 516 . Each counter, based on the prediction success signal outputted by prediction module  501 , tallies the count of prediction successes.  
         [0036]     According to the conventional three-pointer even method for memory management shown in  FIG. 3 , when three path memories are full (marked as WR in the figure), the traceback starts, and the writing to the next path memory can also continue. At the beginning of tracebacking, storage control module  525  refers to the counter of the corresponding decoded bit storage of the first path memory being traced back. If the count is the counter is 16, traceback sub-module  524   a  is shut down and tracebacking is not necessary. Otherwise, tracebacking is required and sub-module  524   a  is activated. The decoded bits during the traceback are recorded in the decoded bit storage corresponding to the path memory being traced back.  
         [0037]     Traceback sub-module  524   b  is for the tracebacking of the second path memory. The operation mode of the tracebacking is similar to that of the traceback sub-module  524   a . Traceback and output sub-module  524   c  is for the tracebacking of the third path memory. The operation mode of the tracebacking is similar to those of the traceback sub-modules  524   a ,  524   b . When finishing tracebacking, the decoded bits stored in the decoded bit storage are all outputted.  
         [0038]      FIG. 7A  shows a flowchart of the prediction method used in the Viterbi decoder of  FIG. 5B . Each counter corresponds to a decoded bit storage.  
         [0039]     As shown in  FIG. 7A , step  701  is to use prediction module  501  to determine, based on a plurality of parameters from the Viterbi decoder and a state of the minimum path metric of the previous stage stored in prediction module  501 , whether the state of the minimum path metric of the current stage is connected to the state of the minimum path metric of the previous stage. If not, stop the prediction method, i.e., de-activate prediction module  501 , until a preset activation condition being met and returning to step  701 .  
         [0040]     According to the present invention, parameters from the Viterbi decoder include a prediction activation signal from storage control module  525 , a path source of each state in the current stage from path computing module  521 , and the state of the minimum path metric of the current stage from path metric comparison module  523 . The preset activation condition is set at the time when the current path memory is full and the writing to the next path memory is about to start. At this time, storage control module  525  sends an activation signal to activate prediction module  501 .  
         [0041]     Step  702  is to generate at least a decoded bit of the current stage, stores sequentially the decoded bit to one of the plurality of decoded bit storages  511 - 51 N, and adjusts the counter corresponding to the decoded bit storage being currently processed. Step  703  is to use a prediction and traceback mechanism to determine whether to directly output all the decoded bits in one of the decoded bit storages at a preset output time. Finally, in step  704 , storage control module  525  transmits a decoded bit signal to decoded bit storage  51 N corresponding to the last path memory  54 N being already traced-back, and decoded bit storage  51 N outputs all decoded bits stored in it.  
         [0042]     The following uses the radix-4 design in  FIG. 6  to explain the prediction method applied in the Viterbi decoder.  
         [0043]     Prediction module  501  uses the plurality of parameters from the Viterbi decoder and the parameter stored in prediction module  501  to determine if the state of the minimum path metric of the current stage is connected to the state of the minimum path metric of the previous stage (as in step  701 ). If connected, the two decoded bits of this stage are generated and stored sequentially to one of the six decoded bit storages, and counter  53 N corresponding to the currently processed decoded bit storage is incremented by 1 (step  702 ). Then a prediction and traceback module is used to determine whether to directly output all the 32 decoded bits in one of the decoded bit storages at a preset output time (step  703 ). Finally, the decoded bit storage corresponding to the last path memory being already traced-back outputs all the 32 decoded bits stored in it.  
         [0044]      FIG. 7B  shows a flowchart for operating the prediction and traceback mechanism according to the present invention. Step  703  in  FIG. 7A  includes the following five steps.  
         [0045]     In step  711 , a test is conducted to determine whether the number of the path memories that are full equals to the preset traceback number. If so, the tracebacking starts and step  712  is taken. Otherwise, repeat step  711 . According to the three-pointer even method for memory management, when three path memories are full, the tracebacking starts and the writing to the next path memory continues.  
         [0046]     In step  712 , a test is conducted to determine whether the current path memory being traced back meets the criteria to waiver the tracebacking. If so, skip to step  715 ; otherwise, take step  713 . As shown in  FIG. 6 , each decoded bit storage is 32-bit and traceback sub-module  524   a  is tracebacking the third path memory. When the counter corresponding to the third path memory equals to 16, it means that the channel condition is good and all the predictions are correct. The traceback sub-module  524   a  can be shut down, and no further traceback is required.  
         [0047]     Step  713  is to use a traceback module to store the decoded bits generated in each stage to the decoded bit storage during tracebacking the corresponding path memory, and determine whether the state of the current stage equals to the combination of the decoded bits of the previous several stages. If so, no further tracebacking is required and step  715  is taken; otherwise, step  714  is taken.  
         [0048]     At the beginning of tracebacking, storage control module  525  refers to the counter of the corresponding decoded bit storage of the first path memory being traced back. If the count in the counter is not 16, sub-module  524   a  is activated and the tracebacking starts with the use of values stored in path memory. Traceback sub-module  524   a  stores the decoded bits to corresponding decoded bit storage. When the number of the traced back stages equals to the sum of the count in the counter and 1, storage control module  525  determines whether the state of the minimum path metric of the current stage equals to the combination of the decoded bits of the previous several stages. If so, it means the paths are overlapping. Then, the counter is set to 16 and traceback sub-module  524   a  is shut down. Otherwise, tracebacking is continued until the end of the path memory is reached. For example, during the tracebacking, when the state of the current stage (6 bits) equals to the effective combination of the decoded bits of the previous three stages, the paths overlap, and the sub-module  524   a  can be shut down. When tracebacking reaches k-th stage, the state is 011100, and the decoded bits of (k-1)th stage, (k-2)th stage, and (k-3)th stage are 00, 11, and 01, respectively, the paths overlap.  
         [0049]     Traceback sub-module  524   b  is for the tracebacking of the second path memory. The operation mode of the tracebacking is similar to that of the traceback sub-module  524   a . Traceback and output sub-module  524   c  is for the tracebacking of the third path memory, and is required to perform tracebacking and decoding. The operation mode of the tracebacking is similar to those of the traceback sub-modules  524   a ,  524   b . When finishing tracebacking, the decoded bits stored in the decoded bit storage are all outputted.  
         [0050]     Step  714  is to determine if the current path memory is completely traced back. If so, proceed the next path memory for tracebacking and take step  715 ; otherwise, return to step  713 .  
         [0051]     Finally, step  715  is to determine whether the number of the traced back path memories equals to the preset number. If so, go to step  704 ; otherwise, return to step  712 . According to the conventional three-pointer even method for memory management, when three path memories are traced back, step  704  can be taken to output all the decoded bits stored in the decoded bit storage corresponding to the third path memory.  
         [0052]     In addition to the path memory of a conventional Viterbi decoder, the present invention also includes decoded bit register (as shown in  FIG. 6 ). When the predicted minimum states are connected, the decoded bits are recorded. During the tracebacking, if the path overlapping is found, no access to the path memory is required for the decoding. Instead, the decoded bits can be directly outputted. When the channel condition is good, that is, the path prediction mechanism is correct, 75% of memory access is saved in comparison to the traceback approach of the conventional Viterbi decoder. The power consumption is greatly reduced.  
         [0053]      FIG. 8  shows the simulation results of the present invention. The simulation meets the IEEE 802.11a specification, with multipath channel delay time T rms =50 ns, frequency offset=40 ppm, and timing offset=40 ppm.  
         [0054]     The simulation simulates the number of traceback of each packet at various data rates. The number of packets is 1000, and each packet is 1000-byte long. In a conventional three-pointer even method, the required traceback is 11947 times at all data rates. However, as it is found that less than 1/5 tracebacks are required when the prediction device is activated. From the simulation results, it shows that the number of memory access is reduced, and the power consumption is also reduced.  
         [0055]     The difference between the present invention and the conventional techniques is that the present invention stores decoded bits in the decoded bit storage, while the conventional techniques store the state value. The conventional techniques require traceback to output decoded bits, while the present invention can directly output the decoded bits when the path overlapping occurs.  
         [0056]     Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.