ACS circuit and viterbi decoder with the circuit

An ACS circuit and a Viterbi decoder with the circuit. The Add-Compare-Select (ACS) circuit comprises: two registers for storing two previous candidate state metrics; a first adder for adding the value stored in the first register and a first branch metric to generate a first addition result; a second adder for adding the value stored in the second register and the first branch metric to generate a second addition result; a comparator for comparing the values stored in the first register and the second register to generate a decision bit; and a multiplexer for selecting either the first addition result or the second addition result as a new output candidate state metric according to the decision bit. Due to the parallel processing of the adders and the comparator, the processing speed of a Viterbi decoder with the ACS will be increased.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to an ACS (Add-Compare-Select) circuit, and in particular to an ACS circuit, in which an adder and a comparator are processing in parallel to increase the processing speed thereof, thereby increasing the processing speed of a Viterbi decoder with the ACS circuit.

2. Description of the Related Art

A PRML (Partial Response Maximum Likelihood) system is used to retrieve EFM (Eight-to-Fourteen Modulation) signals from CD (Compact Disc)/DVD (Digital Versatile Disk). In the PRML system, a Viterbi decoder is usually used to realize the maximum likelihood detection.

FIG. 1(A)is a block diagram showing a conventional Viterbi decoder. Referring to this drawing, a Viterbi decoder typically includes a branch metric generator11, an ACS (Add-Compare-Select) unit12, and a survivor path memory and decoding unit13. The branch metric generator11calculates the metrics corresponding to each branch according to the received data, and outputs them to the ACS unit12. The branch metric generator II calculates the distance, such as mean-square-distance, between the received data and the estimated data of the branch. For each state, the ACS unit12adds the branch metrics of input branches with the related state metric to generate the candidate state metrics, compares and selects the minimum of the candidate state metrics as the new state metric. The decision bit of the ACS unit12, indicating the decision of the state-metric selection, is sent to the survivor path memory and decoding unit13. According to the decision bit, the survivor paths of the survivor path memory and decoding unit13are updating to keep consistent with the selected result of related state metric. The survivor memory and decoding unit13restores the decoded results corresponding to each state, and a decoding unit executes the majority vote for the ending bits of all survivor paths to decide the output decoded result.

FIG. 1(B)is an architecture diagram showing an ACS processor in the ACS unit ofFIG. 1(A), wherein SMi(n−1) and SMj(n−1) are state metrics of state Siand state Sjat time n−1, respectively, and BMi,k(n−1) and BMj,k(n−1) are branch metrics from state Sito state Skat time n−1 and from state Sjto state Skat time n−1, respectively. The SMk(n) is a state metric at time n and the BMk,m(n) is the branch metric from state Skto state Smat time n. In this drawing, it illustrates that the ACS processor is used to select the survivor state metric from either state Sior state Sj. As shown in the drawing, an ACS processor14in an ACS unit12includes two adders15,15′, a comparator16, and a selector17. The ACS processor14employs the adder15to add SMi(n−1) to BMi,k(n−1) to generate a first candidate state metric, and the adder15′ to add SMj(n−1) to BMj,k(n−1) to generate a second candidate state metric. Then, the ACS processor14employs the comparator16and selector17to compare the first candidate state metric with the second candidate state metric, and select the minimum to be outputted to a state register18as the SMk(n). The comparison result, serving as a decision bit, is outputted to the survivor memory and decoding unit13. The adder19belongs to another ACS processor14′.

FIG. 2(A)shows a 4-state trellis diagram, andFIG. 2(B)is a block diagram showing the ACS unit12in the Viterbi decoder corresponding to the trellis diagram ofFIG. 2(A). SinceFIG. 2(A)is a 4-state trellis diagram, the ACS unit12includes four ACS processors121to124and four state registers125to128for storing the state metrics S0to S3, as shown inFIG. 2(B). In addition to transferring the generated metrics back to the state registers125to128, the ACS processors121to124of the ACS unit12further output decision bits to the survivor memory and decoding unit13. The ACS processor121receives the state metrics from the state registers125and127, adds together the state metrics and the related branch metrics, selects a smaller addition result as a survivor metric, stores back to the state register125, and outputs the comparison value (logic 1 or logic 0) serving as a decision bit simultaneously. The ACS processor122receives the state metrics from the state register125and127, adds together the state metrics and the related branch metrics, selects a smaller addition result as a survivor metric, stores back to the state register126, and outputs a comparison value (logic 1 or logic 0) serving as a decision bit simultaneously. The processing methods for the ACS processors123and124are also the same.

FIG. 3shows a circuit of the ACS processor as shown inFIG. 2(B). Referring toFIG. 3, the ACS processor121includes two adders1211,1211′, a comparator1212and a multiplexer1213. The adders1211,1211′ are used to add together the branch metric and the state metric, and the comparator1212is used to compare two output values from the adders1211,1211′. The multiplexer1213selects a value from the output values of the two adders1211,1211′ as a new state metric according to the comparison result of the comparator1212. Meanwhile, the comparison result of the comparator.1212also serves as a decision bit for output. FromFIG. 1(B)andFIG. 3, it is shown that the execution order of the ACS processor is Add→Compare→Select. Because the execution of comparison needs to wait the result of addition, the addition and comparison cannot be executed in parallel, which is a timing bottleneck of a conventional ACS unit.

In the application of decoding an EFM signal, the EFM signal has the property of run length limited (RLL) that the minimum run length of an EFM signal is 3T, where T is a recording unit length. When decoding with respect to the EFM signal, a simplified trellis diagram can be obtained according to the RLL of the EFM signal, as shown inFIG. 4(A). That is, the trellis diagram has six states including state S0(000), state S1(001), state S2(011), state S3(100), state S4(110), and state S5(111), in which the states of (010) and (101) are invalid and not listed due to the minimum run length of 3T. In addition, state S1(001), state S2(011), state S3(100) and state S4(110) only have a branch.FIG. 4(B)is a schematic illustration showing the branch values corresponding to the trellis diagram ofFIG. 4(A). The Viterbi decoder generates all possible input sequences from the trellis diagram, and selects the most possible result as the decoded result. According to the trellis diagram ofFIG. 4(A), only state S0and state S5receive two input values, so the state S0and state S5have to judge and select one of the input sequences.

FIG. 5is an architecture diagram showing a Viterbi decoder applied to the trellis diagram ofFIG. 4(A). Referring to the drawing, the Viterbi decoder includes an ACS unit52and a survivor memory and decoding unit13. Because the trellis diagram has already been simplified due to the property of RLL, the ACS unit52only includes two ACS processors521and522, two adders523and524, and six registers525to530. The ACS processor521receives the state metrics of state S0and state S3, adds together the state metrics and the related branch metrics, selects a smaller result through the compare-select circuit5211, and stores the selected result back to the register525at state S0. Next, the ACS processor521outputs the comparison value, serving as a decision bit, from the compare-select circuit5211to the multiplexers in the path0of the survivor memory and decoding unit13. The ACS processor522receives the state metrics of state S2and state S5, adds together the state metrics and the branch metrics, selects a smaller result through the compare-select circuit5221, and stores the selected result back to the register530at state S5. Next, the ACS processor522outputs the comparison value, serving as a decision bit, from the compare-select circuit5221to the multiplexers in the path5of the survivor memory and decoding unit13. Since the trellis diagram has been simplified, the multiplexers are only arranged in path0and path5of the survivor memory and decoding unit13. Other paths1to4are only used to transfer data directly to another path memory. The survivor memory and decoding unit13employs a decision circuit131, which may be a majority vote circuit, to vote the majority of bit value of the ending bits of six survivor paths as decoded data for output.

U.S. Pat. No. 6,148,431 titled “Add compare select circuit and method implementing a Viterbi algorithm” disclosed an ACS circuit with parallel process in the adder and comparator. In this architecture, the trellis diagram must satisfy the condition that the branch metrics for the ACS unit have to be equal. That is, the ACS unit in the U.S. Pat. No. 6,148,431 is not an ACS unit for general purpose.

In general, the conventional ACS unit is the bottleneck of processing speed of the Viterbi decoder, and the ACS processor of the ACS unit cannot increase the processing speed by way of direct pipelining or parallel processing.

SUMMARY OF THE INVENTION

In view of the above-mentioned problems, an object of the invention is to provide a Viterbi decoder capable of changing the processing order of the ACS processor to make the add and compare units of the ACS processor process in parallel, thereby increasing the processing speed of the Viterbi decoder.

To achieve the above-mentioned object, the invention provides a Viterbi decoder consisting of a branch metric generator, a plurality of ACS units, and a survivor memory and decoding unit. The ACS unit comprises: two registers for storing two previous candidate state metrics; and a ACS processor for receiving the previous candidate state metrics stored in the state registers and a first branch metric, generating a first output candidate state metrics.

The ACS processor comprises a first adder, a second adder, a comparator and a first multiplexer. The first adder adds the value stored in the first register and a first branch metric to generate a first addition result. The second adder adds the value stored in the second register and the first branch metric to generate a second addition result. The comparator compares the values stored in the first register and the second register, and outputs a comparison signal as the decision bit. The first multiplexer selects either the first addition result or the second addition result as the first output candidate state metric according to the comparison signal.

The ACS processor can further comprise a third adder, a fourth adder, and a second multiplexer. The third adder adds the value stored in the first register and a second branch metric to generate a third addition result. The fourth adder adds the value stored in the second register and the second branch metric to generate a fourth addition result. The second multiplexer selects either the third addition result or the fourth addition result as a second output candidate state metric according to the comparison signal of the comparator.

Due to the parallel processing of the adders and the comparator of the ACS processor, the processing speed of the Viterbi decoder is increased.

DETAILED DESCRIPTION OF THE INVENTION

The Viterbi decoder of the invention will be described with reference to the accompanying drawings.

First, please refer back toFIG. 1(B). In the architecture of the ACS processor of a conventional Viterbi decoder, an adding process is firstly executed, and then a compare-select unit is utilized to select the corresponding data to be outputted to the register. That is, the operation order is add→compare→select. Consequently, parallel processing of the adder and comparator can not be directly executed in this architecture. In view of this, the invention rearranges the operation order of the ACS processor to make the adder and comparator process in parallel to increase the processing speed of the ACS processor.

FIG. 6is an architecture diagram showing an ACS processor of the present invention in which the operation order is rearranged. Referring toFIG. 6, the ACS processor60includes a comparator63, a selector65and an adder64. Compared withFIG. 1(B), the present invention moves the state metric register forward from the location behind the selector into the location before the comparator, which has to add an extra state metric register. That is, each ACS unit in the present invention needs more state metric register. The comparator63receives the signals from the two state metric registers62,62′ and outputs a decision bit. Then the selector65selects one of the signals from the two state metric registers62,62′ according to the decision bit and outputs a new state metric. Finally, the adder64adds the state metric outputted from the selector65with a branch metric and outputs the result to another metric registers (not shown). Therefore, the operation order of the ACS processor60is changed into compare→select→add, which is different from the conventional operation order of add→compare→select.

FIG. 7shows the circuit of the ACS processor of the invention, whereinFIG. 7(A)shows an adder arranged in back of a multiplexer, whileFIG. 7(B)shows two adders arranged in front of a multiplexer. As shown inFIG. 7(A), the ACS processor70utilizes the comparator71to compare the values of two candidate state metrics (a, b) and to generate a decision bit, and utilizes the multiplexer72to select a smaller candidate state metric as a survivor state metric according to the decision bit. The candidate state metrics (a, b) are stored in different state registers, respectively. Then, the adder73is utilized to add together the selected survivor state metric and the branch metric (c) to generate a new candidate state metric, which is sent to anther ACS processor. Therefore, the output value O of the ACS processor70is:
O=min(a, b)+c(1).

Substituting the branch metric (c) of Equation (I) into the min function, Equation (1) is converted into Equation (2):
O=min(a+c, b+c)  (2)

FIG. 7(B)shows the circuit of the ACS processor generated according to Equation (2). As shown in the drawing, because the adders73are moved to positions in front of the multiplexer72in the ACS processor75, an extra adder73′ is added, and the adders73,73′ and comparator71can perform parallel processing. Consequently, the ACS processor75has the processing speed defined as (delay time of the adder+delay time of the multiplexer), or (delay time of the comparator+delay time of the multiplexer), which is quicker than the processing speed defined as (delay time of the adder+delay time of the comparator+delay time of the multiplexer) of prior art. In general, the delay time of the adder substantially equals to the delay time of the comparator. Therefore, when the bit length of the state metric is so long that the delay time of the multiplexer can be neglected, the processing speed of the ACS processor75can be substantially doubled.

FIG. 8shows the circuit of the PACS unit related to a state with two output branches. Compared toFIG. 7, it outputs two candidate state metrics of two output branches. The PACS unit80shown inFIG. 8includes a comparator81, two multiplexers82and four adders83. That is, the PACS unit80includes an extra multiplexer82and two extra adders83with respect to the PACS unit75.

FIG. 9is a block diagram showing an ACS unit of the Viterbi decoder according to a first embodiment of the invention. The Viterbi decoder as shown inFIG. 9will be described taking the 4-state trellis diagram ofFIG. 2(A)as an example. The ACS unit90includes four PACS (parallel Add-Compare-Select) unit80for parallel processing, and eight state registers92for storing state metrics. That is, each state branch needs two state registers92and a PACS unit80. The two candidate state metrics outputted from each PACS unit80of the ACS unit90are outputted to two state registers92.

FIG. 10shows the data flow diagram of the ACS unit generated according to the trellis diagram ofFIG. 4(A), whereinFIG. 10(A)shows the data flow diagram of the conventional ACS unit, whileFIG. 10(B)shows the data flow diagram of the ACS unit of the present invention. The bold lines inFIG. 10denote the main data flow. As shown in theFIG. 10(A), the data from the register D must pass through the adder, the comparator, and then the selector. On the other hand, as shown inFIG. 10(B), the data from the register D just passes through the adder and then the selector. In this embodiment, the hardware cost of the invention is increased to 20%˜30% of the original cost. However, the speed is substantially doubled. Therefore, the invention's ACS unit can effectively shorten the data processing time of the ACS processor, thereby increasing the data processing speed of the ACS unit.

While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific construction and arrangement shown and described, since various other modifications may occur to those ordinarily skilled in the art.