Branchmetric Calculation Circuit in a Viterbi Decoder

1. Field of the Invention

The present invention relates to a Viterbi decoder for decoding digital data signals in a data transmission system, in a recorded information reproducing apparatus for reproducing information recorded on a recording medium, or the like, and more particularly, to a branchmetric calculation circuit in such a Viterbi decoder.

2. Description of Background Information

Viterbi decoding is a method for decoding digital data signals affected by inter-code interference, with a high reliability in a recorded data reproducing system such as a recorded information reproducing apparatus as mentioned above. According to the Viterbi decoding, digital data signals can be decoded in a low error ratio even if inter-code interference is large or even if reproduced signals present a low signal-to-noise (S/N) ratio.

FIG. 1 shows a configuration of a Viterbi decoder for realizing the Viterbi decoding as mentioned above. Referring specifically to FIG. 1, signals read from a recording medium on which digital signals are recorded or information signals transmitted from a communication terminal in a digital transmission system are supplied to an analog-to-digital (A/D) convertor 1 as received signals. The A/D convertor 1 samples the received signals at predetermined sampling timing to sequentially convert the received signals to a sample value sequence which is then supplied to a branchmetric calculation circuit 2.

The branchmetric calculation circuit 2 calculates a square error value between each of a plurality of predicted sample values assumed as possible ideal values for the received sample values (values received when the received signals are not affected by noise or the like) and corresponding one of actually received sample values supplied from the A/D convertor 1, as given by the following equation.

The square error values are supplied to the pathmetric calculation circuit 3 as branchmetric values.

FIG. 2 shows an example of an internal configuration of the branchmetric calculation circuit 2.

Referring specifically to FIG. 2, a subtractor 21 subtracts a predicted sample value from a received sample value supplied from the A/D convertor 1, and supplies the subtraction result to a multiplier 22. The multiplier 22 squares the supplied subtraction result to derive the square value as a branchmetric value.

Here, assuming that a transmission system up to the supply of the received signals to the Viterbi decoder is a RP(1, 1) transmission system (partial response transmission class I), a received sample value Y(k) at time k can be predicted from a transmitted sample value X(k) at time k and a transmitted sample value X(K-1) at the preceding time. More specifically, when X(k) and X(K-1) are "0, 0", Y(k) is "0". When X(k) and X(K-1) are "0, 1" or "1, 0", Y(k) is "1". When X(k) and X(K-1) are "1, 1", Y(k) is "2". Stated another way, a received sample value Y(k) supplied to the Viterbi decoder can be predicted in four different ways in accordance with the two transmitted sample values X(k) and X(K-1).

In this event, the branchmetric calculation circuit 2 supplies a pathmetric calculation circuit 3 with four branchmetric values .lambda..sub.00 -.lambda..sub.11 corresponding to these four predicted sample values.

The pathmetric calculation circuit 3 accumulatively adds the values in sequence for each branchmetric value, and utilizes the accumulatively added values as pathmetric values. Then, a pass selecting signal indicative of the pass having the smallest one of these pathmetric values is supplied to a pass memory 4. The pass memory 4, in response to the pass selecting signal, updates a preliminarily determined value consisting of "0" and "1" values, and outputs this as a decoded digital signal.

As described above, the Viterbi decoder calculates a square error between a received sample value and a predicted sample value as a branchmetric, and relies on the branchmetric to decode a seemingly reliable digital signal sequence.

However, for deriving the square error, square calculation processing using the multiplier 22 shown in FIG. 2 is indispensable. The multiplier 22 requires a long time for the calculation due to a delay caused by carry operations performed within the multiplier 22. Thus, the processing time required by the entire Viterbi decoding also becomes longer depending on the time spent for the square calculation. Further, since the multiplier 22 has a large circuit scale, if the Viterbi decoder as shown in FIG. 1 is integrated in a single LSI circuit, its manufacturing cost will be increased.

The present invention has been made to solve the problems mentioned above, and its object is to provide a branchmetric calculation circuit in a Viterbi decoder which is capable of performing high speed decoding in a small circuit scale. The present invention provides a branchmetric calculation circuit in a Viterbi decoder which calculates a square error between a received value and a predicted value as a branchmetric and produces a decoded data sequence based on the branchmetric, comprising subtracting means for subtracting the predicted value from the received value to derive a subtraction value, and broken line converting means for converting the subtraction value using a broken line function for square calculation and utilizing the resulting value as the branchmetric.

The branchmetric calculation circuit in a Viterbi decoder according to the present invention performs the square calculation for deriving a square of a subtraction result value between a received sample value and a predicted sample value using broken line approximation given by a plurality of linear functions.

FIG. 1 is a block diagram showing a configuration of a Viterbi decoder;

FIG. 2 is a block diagram showing a configuration of a conventional branchmetric calculation circuit;

FIG. 3 is a block diagram showing a configuration of a branchmetric calculation circuit according to the present invention;

FIGS. 4-6 are graphs each showing an example of a broken line approximation function for a square calculation performed by the branchmetric calculation circuit of the present invention;

FIG. 7 is a diagram showing a circuit configuration of the branchmetric calculation circuit according to the present invention;

FIG. 8 is shows a truth table for the branchmetric calculation circuit illustrated in FIG. 7;

FIG. 9 is a block diagram showing another configuration of a branchmetric calculation circuit according to the present invention;

FIGS. 10 and 11 are graphs each showing an example of the broken line approximation function for the square calculation performed by the branchmetric calculation circuit of the present invention;

FIG. 12 is a diagram showing an example of a circuit configuration of a branchmetric calculation circuit according to the present invention;

FIG. 13 shows a truth table for the branchmetric calculation circuit illustrated in FIG. 12;

FIG. 14 is a block diagram showing another configuration of a branchmetric calculation circuit according to the present invention;

FIGS. 15 and 16 are graphs each showing an example of the broken line approximation function for the square calculation by the branchmetric calculation circuit of the present invention;

FIG. 17 is a diagram showing a circuit configuration of a branchmetric calculation circuit according to the present invention;

FIG. 18 shows a truth table for the branchmetric calculation circuit illustrated in FIG. 17; and

FIG. 19 is a graph showing an example of the broken-line approximation function for the square calculation by the branchmetric calculation circuit of the present invention.

The present invention will hereinafter be described in connection with several embodiments thereof.

FIG. 3 shows a configuration of a branchmetric calculation circuit according to the present invention.

In FIG. 3, a subtractor 21 subtracts a predicted sample value from a received sample value supplied from the A/D convertor 1 shown in FIG. 1, and supplies the subtraction result value to a broken-line convertor circuit 23.

The broken line convertor circuit 23 converts the subtraction result value using a broken-line approximation function for square calculation to derive a converted value as a branchmetric value. In this event, assuming that the subtraction result value is X, the broken-line approximation function is given by the following linear functions Ya and Yb:

In the broken-line convertor circuit 23 shown in FIG. 3, an absolute value .vertline.X.vertline. of the subtraction result value X is calculated by an absolute value generator circuit 231, and this absolute value .vertline.X.vertline. is bit-shifted by i bits by a bit-shift circuit 23 to realize the linear function Ya. On the other hand, a subtractor 235 subtracts a predetermined constant a from a value derived by bit-shifting the absolute value .vertline.X.vertline. by j bits by a bit-shift circuit 233 to realize the linear function Yb.

In this event, a selector 234 selects the value bit-shifted by the bit-shift circuit 232 as described above as a branchmetric value when the absolute value .vertline.X.vertline. is smaller than a predetermined value t, and selects the value calculated by subtracting the predetermined constant a from the bit-shifted value by the bit-shift circuit 233 as the branchmetric value when the absolute value .vertline.X.vertline. is equal to or lager than the predetermined value t.

FIG. 4 shows a broken line approximation function for the square calculation performed by the broken line convertor circuit 23.

As shown in FIG. 4, when the absolute value of the subtraction result value X is smaller than the predetermined value t, the linear function Ya (indicated by a solid line), the gradient of which is 2.sup.i, is utilized to convert the subtraction result value X, and the converted value is used as a branchmetric value Y. On the other hand, when the absolute value of the subtraction result value X is equal to or lager than the predetermined value t, the linear function (indicated by a broken line), the gradient of which is 2.sup.j, is used to convert the subtraction result value X, and the converted value is used as the branchmetric value Y.

FIG. 5 shows an example of a broken-line approximation function which is applied when the square calculation is performed as Y.sub.p =(1/4).multidot.X.sup.2.

In FIG. 5, the subtraction result value X is an integer value expressed by 4 bits (-8-7), and the shown broken-line approximation function is one derived when i=0 in the linear function Ya, j=1 in the linear function Yb, a=4, and t is equal to one half of a maximum value of the absolute value .vertline.X.vertline., i.e., 4.

Thus, the broken-line approximation function is given by:

In this event, the absolute value generator circuit 23 shown in FIG. 3 supplies the subtraction result value X as it is to each of the bit-shift circuits 232 and 233 when the 4-bit subtraction result value X supplied from the subtractor 21 has its most significant bit set to logical "0", i.e., when the subtraction result value X is a positive integer equal to or less than 7. On the other hand, if the most significant bit of the subtraction result value X is logical "1", i.e., if the subtraction result value X is a negative integer equal to or more than -8, the absolute value generator circuit 23 inverts the logical states of all 4 bits of the subtraction result value X, adds 1 to the inverted value, and supplies the resulting value as the absolute value .vertline.X.vertline. to each of the bit-shift circuits 232 and 233. Here, since i=0 is assumed in the bit-shift circuit 232, as mentioned above, the bit-shift circuit 232 supplies the absolute value .vertline.X.vertline. as it is to the selector 234 without performing the bit shifting. On the other hand, the bit-shift circuit 233 supplies the subtractor 235 with a value derived by bit-shifting the absolute value .vertline.X.vertline. by 1 bit toward the most significant bit. The subtractor 235 supplies the selector 234 with a value subtracted 4 from this value. The selector 234 selects the value bit-shifted in the bit-shift circuit 232 in the foregoing manner as the branchmetric value when the absolute value .vertline.X.vertline. is smaller than 4. On the other hand, the selector 234 selects the value derived by subtracting the predetermined constant a from the bit-shifted value in the bit-shift circuit 283 as the branchmetric value when the absolute value .vertline.X.vertline. is equal to or larger than 4.

As described above, in view of the operation of the Viterbi decoding which performs decoding of a seemingly reliable data sequence by selecting a sequence which has the smallest accumulated sum of branchmetric values, the present invention realizes the square calculation performed by the branchmetric calculation circuit using the broken-line approximation given by a plurality of linear functions. Stated another way, in the Viterbi decoding, the value of branchmetric itself is not important, but what is important is to determine which of branchmetric values derived corresponding to a plurality of decoded sequences presents the smallest value. In other words, what is required is only relative comparison among respective branchmetric values, so that decoding accuracy will not be degraded even if the broken-line approximation given by a plurality of linear functions is applied to derive branchmetric values without using the square calculation for the branchmetric values.

Thus, the present invention enables the operation for deriving the branchmetric values to be faster than the conventional branchmetric calculation circuit which uses a multiplier for the square calculation for deriving branchmetric values.

It should be noted that while in the embodiment shown in FIG. 5, the converting functions for the subtraction result value X in the range of positive integer values and the converting functions for the subtraction result value X in the range of negative integer values are symmetric to the ordinate axis, the converting functions may be asymmetric.

FIG. 6 shows another example of a broken-line approximation function created in view of the above-mentioned aspect. The broken-line approximation function shown in FIG. 6 is composed of five linear functions Ya-Ye as follows:

FIG. 7 shows an example of a circuit configuration of a broken-line convertor circuit 23 which derives branchmetric values using the five linear functions Ya-Ye.

Referring specifically to FIG. 7, each bits X.sub.0 -X.sub.3 in a subtraction result value X supplied from the subtractor 21 shown in FIG. 3 are input to exclusive OR circuits EX1-EX3. The exclusive OR circuit EX1 takes exclusive OR of bits X.sub.2 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to a selection terminal S of each of selectors SE1-SE4. The exclusive OR circuit EX2 takes exclusive OR of bits X.sub.1 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to each of an input terminal P.sub.1 of the selector SE1, an input terminal P.sub.0 of the selector SE3, and an invertor IV1. The invertor IV1 inverts a logical value of the exclusive OR output supplied from the exclusive OR circuit EX2, and supplies the inverted logical value to an input terminal P.sub.1 of the selector SE2. The exclusive OR circuit EX3 takes exclusive OR of bits X.sub.0 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to each of an input terminal P.sub.1 of the selector SE3 and an input terminal P.sub.0 of the selector SE4.

The selectors SE1-SE4 are 2-to-1 selectors each composed of an invertor IV2, AND gates AN1 and AN2, and an OR gate OR1. When the selectors SE1-SE4 are supplied at their respective selection terminals S with a logical value "0", they select the signals supplied to their input terminals P.sub.0 as branchmetric values Y.sub.0 -Y.sub.3, respectively. On the other hand, when a logical value "1" is supplied to the selection terminals S of the selectors, they select the signals supplied to their input terminals P.sub.1 as the branchmetric values Y.sub.0 -Y.sub.3, respectively.

As described above, the broken-line approximation function shown in FIG. 6 can be implemented by a relatively small scale logical circuit as shown in FIG. 7.

It should be noted that the foregoing embodiments realizes the broken-line approximation for the square calculation using a two-step broken line, the present invention is not limited to this particular configuration using the two-step broken line.

FIG. 9 shows a configuration of a branchmetric calculation circuit including a broken-line convertor circuit 23 which performs the broken-line approximation for the square calculation using a four-step broken line.

Referring specifically to FIG. 9, a subtractor 21 subtracts a predicted sample value from a received sample value supplied from the A/D convertor 1 in FIG. 1, and supplies this subtraction result value to the broken line convertor circuit 23.

The broken-line convertor circuit 23 converts the subtraction result value using the broken line approximation function for the square calculation and derives a converted value as a branchmetric value. In this event, the used broken line approximation function is given by the following linear functions Ya-Yd:

In the broken line convertor circuit 23 shown in FIG. 9, an absolute value .vertline.X.vertline. of the subtraction result value X is generated in an absolute value generator circuit 231. Then, this absolute value .vertline.X.vertline. is bit-shifted by i bits in a bit-shift circuit 241 to realize the linear function Ya. Also, from a value derived by bit-shifting the absolute value .vertline.X.vertline. by j bits in a bit-shift circuit 242, a predetermined constant a is subtracted in a subtractor 246 to realize the linear function Yb. Further, from a value derived by bit-shifting the absolute value by k bits in the bit-shift circuit 243, a predetermined value b is subtracted in the subtractor 247 to realize the linear function Yc. Furthermore, from a value derived by bit-shifting the absolute value .vertline.X.vertline. by 1 bits in a bit-shift circuit 244, a predetermined value c is subtracted in a subtractor 248 to realize the linear function Yd.

In this event, a selector 245 selects the value derived by the bit-shift operation in the bit-shift circuit 241 as a branchmetric value when the absolute value .vertline.X.vertline. is smaller than t.sub.1. Also, the selector selects the value derived by subtracting the predetermined constant a from the value bit-shifted in the bit-shift circuit 242 as a branchmetric value when the absolute value .vertline.X.vertline. is equal to or more than t1 and less than t.sub.2. Further, the selector 245 selects the value derived by subtracting the predetermined constant b from the value bit-shifted in the bit-shift circuit 243 as a branchmetric value when the absolute value .vertline.X.vertline. is equal to or more than t.sub.2 and less than t.sub.3. Furthermore, the selector 245 selects the value derived by subtracting the predetermined constant c from the value bit-shifted in the bit-shift circuit 244 as a branchmetric value when the absolute value .vertline.X.vertline. is larger than t.sub.3.

FIG. 10 shows a broken line approximation function when the above-mentioned t.sub.1 is chosen to be 2 which is a quarter of the maximum value of the absolute value .vertline.X.vertline.; t.sub.2, 4 which is a half of the maximum value of the absolute value .vertline.X.vertline.; and t.sub.3, 6 which is three quarters of the maximum value of the absolute value .vertline.X.vertline., in addition to i=-1, j=0, k=1, l=2, a=1, b=5, and c=17. In this event, the broken line approximation function is given by the following equations:

Further, FIG. 11 shows an example of a broken line approximation function for performing broken line approximation for the square calculation using a seven-step broken line.

The broken-line approximation function shown in FIG. 11 is composed of seven linear functions Ya-Yg as follows:

FIG. 12 shows an example of a circuit configuration of a broken line convertor circuit 28 for deriving branchmetric values using the above seven linear functions Ya-Yg, and FIG. 13 shows a truth table for the circuit illustrated in FIG. 12.

Referring specifically to FIG. 12, each of bits X.sub.0 -X.sub.3 in a subtraction result value X supplied from the subtractor 21 shown in FIG. 9 is supplied to exclusive OR circuits EX4-EX6. The exclusive OR circuit EX4 takes exclusive OR of bits X.sub.2 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to a selection terminal S2 of respective selectors SE5-SE8. The exclusive OR circuit EX5 takes exclusive OR of bits X.sub.1 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to a selection terminal S1 of the respective selectors SE5-SE8. The exclusive OR circuit EX6 takes exclusive OR of bits X.sub.0 and X.sub.3 of the subtraction result value X, and supplies the exclusive OR output to each of an input terminal P.sub.3 of a selector SE6, input terminals P.sub.1 and P.sub.2 of a selector SE7, and an invertor IV3. The invertor IV3 inverts the logical value of the exclusive OR output supplied from the exclusive OR circuit EX6, and supplies the inverted logical value to an input terminal P.sub.1 of a selector SE8.

The selectors SE5-SE8, which are 4-to-1 selectors each composed of gates G1-G5 as illustrated, select signals supplied to their input terminals P.sub.0 as branchmetric values Y.sub.0 -Y.sub.3, respectively, when a logical "0" signal is supplied to their respective selection terminals S1 and S2. Also, the selectors SE5-SE8 select signals supplied to their input terminals P.sub.1 as the branchmetric values Y.sub.0 -Y.sub.3, respectively, when a logical "1" signal and a logical "0" signal are supplied to their respective selection terminals S1, S2. The selectors SE3-SE8 select signals supplied to their input terminals P.sub.2 as the branchmetric values Y.sub.0 -Y.sub.3, respectively, when a logical "0" signal and a logical "1" signal are supplied to their respective selection terminals S1 and S2. The selectors SE3-SE8 select signals supplied to their input terminal P.sub.3 as the branchmetric values Y.sub.0 -Y.sub.3, respectively, when a logical "1" signal is supplied to their respective input terminals S1 and S2.

As described above, the broken line approximation function shown in FIG. 11 can be implemented in a relatively small scale logical circuit as shown in FIG. 12.

Also, in the calculation of the branchmetric using the broken line approximation function as mentioned above, a maximum value may be set to calculated branchmetric values. Stated another way, since a branch having a branchmetric larger than a certain value or a pass including this branch is selected with a quite low probability, the decoding performance will not degraded even if a maximum value of the branchmetric value is limited.

FIG. 14 shows an example of a configuration in which a so-called limiter function for limiting the maximum branchmetric value to a certain value is added to the branchmetric calculation circuit shown in FIG. 3. In FIG. 14, the functional blocks identical to those in FIG. 3 are designated the same reference numerals.

In the configuration shown in FIG. 14, if an absolute value .vertline.X.vertline. of a subtraction result value X generated in the absolute value generator circuit 231 is larger than a predetermined limit value, a selector 234' outputs a fixed value Lm as a branchmetric value. FIG. 15 shows an example of a broken line approximation function for which an upper limit value is set to 7, a lower limit value to -7 and a fixed value Lm to 10. The broken line approximation function shown in FIG. 15 is given by the following equations:

FIG. 16 shows another embodiment of a broken line approximation function for which an upper limit value is set to 7, a lower limit value to -8 and a fixed value Lm to 10. The broken line approximation function shown in FIG. 16 is given by the following equations:

FIG. 17 shows an example of a circuit configuration of a broken line convertor circuit 23 for deriving branchmetric values using the above six linear functions Ya-Yf, and FIG. 18 shows a truth table for the circuit illustrated in FIG. 17.

Referring specifically to FIG. 17, a 5-bit subtraction result value X consisting of bits X.sub.0 -X.sub.4 is supplied to exclusive OR circuits EX7-EX10 from the subtractor 21 shown in FIG. 14. The exclusive OR circuit EX7 takes exclusive OR of bits X.sub.4 and X.sub.3 in the subtraction result value X, and supplies the exclusive OR output to each of OR gates OR2-OR4. The exclusive OR circuit EX8 takes exclusive OR f bits X.sub.4 and X.sub.2 in the subtraction result value X and supplies the exclusive OR output to the OR gate OR2. The exclusive OR circuit EX9 takes exclusive OR of bits X.sub.4 and X.sub.1 in the subtraction result value X and supplies the exclusive OR output to the OR gate OR3. The exclusive OR circuit EX10 takes exclusive OR of bits X.sub.4 and X.sub.0 in the subtraction result value X and supplies the exclusive OR output to the OR gate OR4. The OR gate OR2 takes logical OR of the exclusive OR outputs supplied from the exclusive OR circuits EX7 and EX8, and supplies the resulting logical OR to a selection terminal S of respective selectors SE9-SE12. The OR gate OR3 takes logical OR of the exclusive OR outputs supplied from the exclusive OR circuits EX7 and EX9, and supplies the resulting logical OR to each of an input terminal P.sub.1 of the selector SE9, an input terminal P.sub.0 of a selector SE11, and an invertor IV5. The invertor IV5 inverts the logical value of the logical OR supplied from the OR gate OR3, and supplies the inverted logical value to an input terminal P.sub.1 of the selector SE10. The OR gate OR4 takes logical OR of the exclusive OR outputs supplied from the exclusive OR circuits EX7 and EX10, and supplies the resulting logical OR to each of an input terminal P.sub.1 of the selector SE11 and an input terminal P.sub.0 of the selector SE12.

The selectors SE9-SE12 are 2-to-1 selectors which have the same internal configuration as the selectors SE1-SE4 shown in FIG. 7. The selector SE9-SE12 select the signals supplied to their input terminals P.sub.0 as branchmetric values Y.sub.0 -Y.sub.3, respectively, when a logical "0" signal is supplied to its selection terminal S, and select the signals supplied to their input terminals P.sub.1 as the branchmetric values Y.sub.0 -Y.sub.3 when a logical "1" signal is supplied to the selection terminal S.

As described above, by providing the limiting function in the branchmetric calculation circuit, the number of bits required to the calculation can be reduced, so that the scale of circuit subsequent to the branchmetric calculation circuit, i.e., a circuit for pathmetric calculation can also be reduced.

It should be noted that in the foregoing embodiments, the respective linear functions for the broken line approximation function are continuous, they may be discontinuous as indicated by a solid line in FIG. 19.

It will be appreciated from the foregoing description that the branchmetric calculation circuit in a Viterbi decoder according to the present invention is configured to perform the square calculation for deriving a square value of a subtraction result value between a received sample value and a predicted sample value in the form of broken line approximation using a plurality of linear functions.

It is therefore possible, according to the present invention, to realize faster processing with a smaller scale circuit configuration as compared with a conventional branchmetric calculation circuit which derives branchmetric values by the square calculation processing using a multiplier.