A. Field of the Invention
The invention relates to a decoding circuit and a decoding method of a Viterbi decoder in a Partial Response Maximum Likelihood (PRML) system of an optical disc. Particularly, the invention relates to a decoding circuit and a decoding method for a Viterbi decoder in a PRML system of an optical disc wherein a run length limited code (RLL Code) is used for effectively simplifying the complicated trellis diagram of the Viterbi decoder after longitudinal arrangement without a lot of registers for data processing.
B. Description of the Related Art
In a PRML system such as a digital versatile disc (DVD) or the like, a trellis diagram can be used for describing the property of a transmission channel with a memory. For example, an input signal EFM (eight to fourteen modulation) of a DVD channel is a binary signal and the channel memory length is 2. Accordingly, the trellis diagram has four states each having two branches. Thus, each state has eight branches and it means that the signal outputted from the transmission channel at each time is one of the eight possible signals. As shown in FIG. 1A which is a schematic illustration showing the channel model, the values of the eight possible signals can be obtained from the channel model by substituting the (1/−1) as the “current input” into the following equation:(“current input”+k1*“previous input in the first memory”+k2*“previous input in the second memory”)
In FIG. 1A, k1 and k2 represent the characteristic of the channel. The values of k1 and k2 may be given in advance. Then, a shaping filter, which is a partial response equalizer, is used for making the characteristic of the whole channel approach the values. Alternatively, in a method of signal level estimation, the values of k1 and k2 are directly estimated without changing the characteristic of the channel. No matter which method is adopted, the corresponding values on each branch of the trellis diagram in FIG. 1B will be determined after the values of k1 and k2 are determined.
FIG. 2 is a block diagram showing a Viterbi decoder. In FIG. 2, a Viterbi decoder 200 includes a branch metric unit 202, an ACS (add-compare-select) 204, and a path memory unit (PMU) 206. The branch metric unit 202 receives a digital signal outputted from a pre-stage converter (not shown) and a reference level outputted from a reference-level generating unit (not shown) and computes a branch metric BM. The ACS 204 receives the branch metric BM and performs the operations of adding, comparing and selecting according to the branch metric so as to obtain a path metric PM. The path memory unit 206 receives the path metric PM outputted from the ACS 204 and performs the operations of converging, merging and decoding to obtain a decoded signal, which is outputted to a next-stage demodulator (not shown). The Viterbi decoder 200 is further described in detail in the following.
FIG. 3 is a schematic illustration showing a decoding deduction for the Viterbi decoder. In FIG. 3, if the Viterbi decoder 200 continuously receives three signals R1, R2 and R3 and will find out the most possible corresponding signal, it firstly computes (performed by the branch metric unit 202 in FIG. 2) the branch metric with respect to each branch in the trellis diagram. The computation method is usually of computing the square value of the signal difference or the absolute value of the signal difference, for example, BM00-00=[R1−(−1.8)]2 or |R1−(−1.8)|. The so-called “path metric of a certain path” means the addition result of all branch metrics corresponding to all branches of this path. For example, the path metric of the path from State00 at 1T, State00 at 2T, state01 at 3T, and finally to State11 at 4T, indicated by the bold lines in FIG. 3, is “BM00-00=BM00-01+BM01-11”.
Of course, under the general condition, the path will never be so short. The above-mentioned path before State00 at 1T should travel a certain path. Thus, the actually correct path metric of the path should be “the path metric accumulated to State00 at 1T in this path”+“BM00-00+BM00-01+BM01-11”. It can be understood from the trellis diagram that each path crosses with one another on each state, and that the variations after each state for any arbitrary path are all the same. Therefore, Viterbi found that an optimum path would be determined finally as long as the optimum path at each state is selected for continuous extension. However, the degree of operating complication can be greatly decreased. The operation of “selecting an optimum path at each state for continuous extension” is known as a survivor path selection and the selected path is a survivor path.
In FIG. 3, it describes how the survivor path at State00 at 2T is selected from the survivor path at State00 at 1T and the survivor path at State10 at 1T. Referring to FIG. 3, the survivor metric SM00 at 2T at State00 at 2T is obtained from the following equation:SM00 at 2T=min{[SM00 at 1T+BM00-00]; [SM10 at 1T+BM10-00]}
This equation is performed by the ACS unit. Since a feedback loop exists in the ACS unit (the survivor metric of each state has to be re-calculated), it is difficult to implement a high-speed Viterbi decoder. Thus, the ACS becomes the bottleneck of speed.
According to the deduction of the Viterbi decoder, after each opeartion of the ACS, an optimum path can be surely obtained. Thus, as long as each survivor path is continuously recorded, the optimum path can be obtained by transforming the record of the optimum survivor path after the whole data are decoded. However, there are two disadvantages in this case. First, the hidden decoding path is too long. Second, if the path is too long, the capacity of the hardware for recording will be relatively great (the hardware is called a path memory unit).
Referring to FIG. 4, which is a schematic illustration showing the convergence in the trellis diagram using the algorithm of the Viterbi decoder, the Viterbi algorithm possesses a property that each survivor path has 99% opportunity to merge with its pervious path after the trellis extending four to six times of the length of the channel memory. Therefore, it is only necessary for the path memory unit to keep the latest data within four to six times of the channel memory for selection. The forgone data can be discarded after each decoding operation. Thus, the operation of the path memory unit can be completed using limited resources. The commonly used methods include the shuffle-exchange and trace-back methods.
FIG. 5 shows the trellis diagram and a block diagram of the shuffle-exchange method. In FIG. 5, the operation principle of the shuffle-exchange is to provide a set of memories (register arrays are often used) corresponding to each state on the trellis diagram. For example, the state “00” corresponds to the register array 502, the state “01” corresponds to the register array 504, the state “10” corresponds to the register array 506, and the state “11” corresponds to the register array 508. These register arrays are used for recording the survivor paths of the states.
That is, the survivor paths recorded in each state at a specific time are continuously replaced by the survivor paths recorded in each state at a previous time as well as the newly decision bits (the values of −1.8, −0.8, 0.2, 1.2, −1.2, −0.2, 0.8, 1.8 as shown in FIG. 5). As shown in FIG. 5, when the received signals passes about 4 to 6 times of the length of the channel memory, it can be assumed that all paths have been converged to one point. Thus, the converged values can be sent as the decoded signals. Consequently, the length of each register array only has to be about 4 to 6 times of the channel memory.
FIG. 6 shows a trellis diagram and a block diagram of a trace-back method. As shown in FIG. 6, the operation principle of the trace-back method is to store the decision bits of each state (at each time) into a “regular memory” such as a RAM. That is, each state regularly stores its decision bits. For example, the decision bits of the state “0” is stored in a first row of the RAM, the decision bits of the state “01” is stored in a second row of the RAM, and so on. No interaction exists between any two states. After 4 to 6 times of the length of the channel memory is passed, as shown in FIG. 4, a converged point (root) appears. Therefore, from an arbitrary state, the stored decision bits can be used for deriving a previous state and finding the root by the trace-back method.
However, in the actual implemenattion, it is not possible to perform such a trace-back operation for finding each root. Instead of this trace-back operation, a method of batch operation is used for arranging the data to the configuration of “finding the root, and then finding a piece of data sequentially”. This method can be described by four basic operations of V (write-in), T (trace), I (idle), and D (decode).
FIG. 7 is a schematic illustration showing the relationship between the time and space of the four basic operations in the trace-back method. Referring to FIG. 7 along the vertical direction at first, the memory M1 regularly writes-in (V operation) the decision bits of each state at T1. Next, the trace-back operation (T operation) is performed from a certain state to solve the root at T2. When the root is found, the operation is transferred to the memory M4 (adjacent blocks are recorded on the trellis and then the block M4 decodes (D operation) the decision bits after the root). At T3, the data of the memory M1 is temporarily idled (I operation), because it is not a long time since the previous write-in (V) process is performed. The data within the memory M1 can be regarded as being merged only after the trellises are merged. At this time, the root generated from the memory M2 is given to the memory M1 for performing the decoding process (D operation).
Again, referring to FIG. 7 along the horizontal direction, at certain timing, each memory block performs the four basic operations of V, D, I, and T. The advantage of the trace-back method is the regular operation thereof. Since each state in the same stage is stored individually, the difficulty of layout is decreased. The disadvantage of the trace-back method is that it is usually implemented using RAMs. Thus, it is allowable for the application of DVD players but is not allowable in DVD ROMs due to its slow speed. If registers are used for increasing the speed, a lot of hardware costs should be paid because four blocks are processing the data simultaneously in the trace-back method. Thus, this method is not suitable for high-priced memories.