1. Field of the Invention
The present invention relates to a Viterbi decoder for decoding data using a trellis diagram, and more particularly to a Viterbi decoder for decoding data using circulation type decoding units connected in parallel.
2. Description of the Related Art
Due to the recent development of communication technology, wireless mobile communication technology has spread worldwide. In a wireless mobile communication environment, data is wirelessly transmitted and received, and thus it is difficult for a receiving side to accurately receive the data transmitted from a transmitting side. In other words, in a data transmission process, the data that is received may be distorted due to the effect of noise and other factors. In order to reduce the distortion, the transmitting side typically encodes the data to be transmitted and the receiving side decodes the encoded data that is received. In addition, the coding and decoding processes are performed in storing data on a recording medium, such as a Digital Versatile Disk (DVD).
Various coding methods have been employed, such as a block coding method, a convolution coding method, and others. The block coding method is a coding method that includes additional data of specified bits in input data bits and encodes the input data. The convolution coding method is a coding method that stores previously input data using a memory and encodes the data based on a correlation between the present input value and the previous input value. The convolution coding method has an excellent error correction efficiency in comparison to the block coding method, and thus it has been generally used.
A Viterbi decoder decodes data that has been coded by the convolution coding method. The Viterbi decoder corrects an error by determining an optimal path from a resultant value that is accumulated through a multistage operation.
FIG. 1 is an exemplary view illustrating a trellis diagram used in a general Viterbi decoder. In the trellis diagram illustrated in FIG. 1, a constraint length is 3 and a coding rate is 1/2. Since the constraint length is 3, the previously input value may be in four states, such as 00, 10, 01, and 11. The Viterbi decoder performs back-tracking of the optimal path that corresponds to the minimum accumulated distance value after a specified time, using a difference between an inherent code allocated to each branch of the trellis diagram and an actually input value as a distance value (e.g., metric). Specifically, if the optimal path passes a branch indicated as a solid line of the trellis diagram, the Viterbi decoder decodes it with “0”, while if the optimal path passes a branch indicated as a dotted line, the decoder decodes it with “1”. Accordingly, it is possible to correct an error even if there is a difference between the received signal and the transmitted signal.
Meanwhile, respective nodes a, b, c and d on the trellis diagram calculate the shortest distances to a destination using Equation (1).Di,j=min{Dk,l+dij,kl,(k,l)∈S(i,j)}  Equation (1)
In Equation (1), Dk,l is the shortest distance from a cell (k, l) to a destination, dij,ki is a local distance between a cell (i,j) and a cell (k,l), S(i,j) is a set of cells around the cell (i, j), and min is a function that outputs minimum value of enumerated items.
In a conventional Viterbi decoder, all nodes of the trellis diagram are not implemented by hardware, but only nodes corresponding to one column are implemented by hardware. Thus, the nodes perform the operation as expressed in Equation (1) (i.e., an addition of the accumulated distance value transferred from the previous nodes to the distance value of each branch, with the lapse of time, selecting the minimum value among the added values, and then storing the resultant value in a memory).
Accordingly, if the operations are performed until the last destination is reached, the optimal path can be found using data stored in the memory. This operation requires additional hardware such as a memory. In addition, since the back tracking process for the optimal path calculation should be performed in the memory, time for the decoding operation is lengthened.
In order to solve the above-described problems, Korea Patent Registration No. 10-0412934 discloses a circulation type Viterbi decoder in which cells are arranged in places corresponding to the respective nodes of a trellis diagram, and the cells corresponding to the last node are connected with the cells corresponding to the first node. In this circulation type Viterbi decoder, it is not necessary to store output values of the respective cells in a separate memory, and thus additional hardware is not required. Also, since the decoding is performed by sensing a change of the last output pulse after a specified trigger signal is applied to the respective cell, the back tracking process is unnecessary. As a result, the decoding time is reduced. However, the circulation type Viterbi decoder also starts the decoding operation for the next bit after the decoding of one bit is completed, and this causes the decoding speed to be lowered as much as the time required for the decoding of the respective data bits.