JP3448679B2 - Viterbi decoder - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an improvement of a Viterbi decoder used for reproducing digital signals such as magnetic disks, optical disks and magneto-optical disks.

[0002]

2. Description of the Related Art In recent years, optical discs have been spotlighted as external storage media for computers. Magneto-optical discs are positioned as the center of memory for storing increasing data in the rapidly developing multimedia fields, from those for recording / reproducing image information to those capable of recording codes for computers. , The applications are expanding rapidly.

A Viterbi decoder is often used in reproducing a digital signal recorded on a magneto-optical disk. The Viterbi decoder is a decoder that estimates the most probable data series as a data series by using the values of the sampling data before and after the focused sampling data, and includes the sampling data from the possible data series. Estimate the most probable data series from the magnitude of each path metric by calculating each branch metric that indicates the probability of transition to the data series and each path metric that indicates the probability that those data series are the original input data series. To do.

The Viterbi decoder has a structure as shown in the block diagram of FIG. 1, and a sampling value y _t converted into a digital signal by an A / D converter (not shown) and input.
A branch metric calculation unit 10 that calculates a branch metric based on the above; an ACS (Add-Compare-Select) circuit 11 that calculates a path metric using the branch metric; and a path metric memory 13 that stores the calculated path metric. , A path memory 12 for storing data corresponding to the obtained path metric and outputting finally determined data.

The operation of the Viterbi decoder having such a configuration will be described below. For example, when the original data is a data series having a constraint length of 4, as shown in FIG. 12, the state of the data series is (0, ₀ , 0) is S ₀ , and the state of (1, ₀ , 0) is S ₁ , The state of (0,1,0) is S ₂ , the state of (1,1,0) is S ₃ , the state of (0,0,1) is S ₄ , and the state of (1,0,
The state of 1) is S ₅ , the state of (0, 1, 1) is S ₆ ,
The state of (1,1,1) is S ₇ , and the time points t−3, t−
The values of the data series at 2, t-1 and t are (c, b,
a, s). In this case, time points t-3, t-2, t-
There are 16 possible combinations of transition from each state of 1 to each state of time points t-2, t-1, and t, and the theoretically expected reproduction level of each combination when ideal decoding is performed. The expected value P ₀ , ..., P ₁₅ is P ₀ , ..., P ₁₅ = a + b
It is given by + c + s.

The sampling value y _t at time _t is shown in FIG.
Is sent to the branch metric calculation unit 10 and the branch metric indicating the probability of transition to the data series of 16 types with respect to the expected value is calculated based on the sampling value y _t according to the flowchart shown in FIG. These 16 branch metrics BM ₀ ~
BM ₁₅ is specifically calculated according to the following equation.

BM ₀ = | y _t −P ₀ | BM ₁ = | y _t −P ₁ | BM ₂ = | y _t −P ₂ | _{· BM 13 = | y t -P} 13 | BM 14 = | y t -P 14 | BM 15 = | y t -P 15 |

The calculated branch metric is ACS times.
It is input to the path 11. The ACS circuit is shown in FIG. 14, for example.
The configuration of the branch metric calculation unit 10 is
16 types of branch method input from each calculation unit
To the memory unit of the path metric memory 13
To PMM₀~ PMM₇At time t-1 stored in
8 types of path metrics are added to the adder Add₀~ Add
₇, Add₈~ Add ₁₅Add by. ACS circuit
Is the path metric after addition to the comparator Com₀~ Co
m₇Compare two by two and select Sel₀~ Sel₇
, The smaller one is selected. That selected
Smetric is the path metric at the new time t
As a memory unit PMM₀~ PMM₇Stored in
Also, the data D corresponding to the selected path metric₀~ D
₇Is supplied to the path memory 12 of FIG.

FIG. 15 is a block diagram showing a configuration example of the path memory 12. The path memory 12 has eight systems (D ₀ to
D ₇ ) In each, shift register 31 and selector 3
This is a configuration in which two sets are provided and a plurality of stages are provided. Each shift register 31 operates in synchronization with a clock, but a selector 32 is provided in front of the shift register 31 so that data to be entered into the shift register 31 is selected.

Each of the eight systems of the path memory 12 has a path memory.
Data D selected by lick₀~ D ₇Is entered. So
The input data of is calculated by the expected value in Fig. 12 and the expected value.
It is determined according to the calculated branch metric. Choice
The device 32 displays the figure according to the value of "1" or "0" input.
Judgment of certain state transition from 12 and all of the system
The shift register 31 of the
The data at time t-1 is the data at time t. like this
The shift register 31 and the selector 32 of each system perform various operations.
By repeating this for each sampling,
State transitions are confirmed, and the sequence of confirmed state transitions
When the data series is confirmed by the occurrence of path merge,
8 lines D on the downstream side in the memory 12₀~ D₇In
Each shift register 31 has the same data and detects this
Output as the data.

[0011]

In the ACS circuit of the Viterbi decoder described above, the branch metric value is added to the path metric value one after another, so that the path metric value becomes large and the number of significant digits required for calculation is large. (Number of bits) becomes very large. Therefore, there is a problem that overflow occurs, resulting in malfunction.

To solve this problem, an ACS circuit as shown in FIG. 16 is known. This ACS circuit has 16 inputs from a branch metric calculator (not shown).
The branch metric, which is a 7-bit bus signal, is stored at the time t stored in the path metric memory 13.
The eight types of path metrics at −1 are added by the adder 14. The added path metric is compared two by two by the comparator 16, and the selector 15 selects the smaller one. The minimum value is selected by the minimum value selector 21 from the selected eight kinds of path metrics. The subtraction circuit 22 subtracts the selected minimum value from each of the eight types of path metrics, and stores them in the path metric memory 13 as the path metrics at the new time t.

However, the path metric value is a bus signal, and in this ACS circuit, all path metric values must be compared with each other in order to select the minimum value, so the circuit scale becomes large. Therefore, as shown in the time chart of FIG. 17, the calculation time for selecting the minimum value (Min.S
el. ) Is too large compared to other computation times,
There was a problem that the processing speed could not be increased.

Further, in recent years, the capacity of magnetic disks and magneto-optical disks has been increased, and high data transfer rates have been demanded. Since the Viterbi decoder operates in clock synchronization, each operation must be executed at high speed in order to obtain a high data transfer rate. The operation speed of the Viterbi decoder is limited by the operation speed of the ACS circuit that must be operated in one clock, which has been an obstacle to increasing the data transfer speed of the Viterbi decoder.

In order to solve such a problem, there is a Viterbi decoder which determines whether or not it is necessary to subtract from a path metric value, determines a subtraction amount each time it is determined to be necessary, and executes a subtraction operation. As disclosed in Japanese Patent Laid-Open No. 6-252780, when the constraint length becomes large, there is a problem that the processing speed sharply slows down because of the necessity of subtraction. Also,
A maximum likelihood detection decoder and an information reproducing device for averaging the calculation time of the branch metric value based on the modification of the formula to shorten the calculation time are disclosed in Japanese Patent Laid-Open No. 9-139678. Depending on the final transformed formula,
There is a problem that some calculations are easy and some are complicated.
The present invention has been made in view of the above-mentioned circumstances, in which overflow and underflow do not occur,
Moreover, it is an object of the present invention to provide a Viterbi decoder capable of high speed operation.

[0016]

A Viterbi decoder according to a first aspect of the present invention calculates each branch metric indicating the probability of transition from a possible data series to a data series including sampling data, and calculates each branch metric. In addition, each path metric indicating the probability that the data series that can be obtained one sampling before is the original data series is added, and the values obtained by addition are compared, and the value with high probability is selected, and each selected In the Viterbi decoder that estimates the most probable data sequence based on each data sequence corresponding to the value, means for subtracting the first predetermined value from each selected value, and each result subtracted by the means means for determining any one or less or not than a second predetermined value, when it is determined that said means is small, the values of said selected and each new path metrics Selected, when the unit determines that not is characterized in that it comprises means for selecting the respective result of the subtraction as each new path metric.

In this Viterbi decoder, the values obtained by adding each branch metric and each path metric are compared with each other to select a value with high certainty. The means to subtract
The first predetermined value is subtracted from each of the selected values, and the determination means determines whether any of the subtracted results is smaller than the second predetermined value. The selecting means selects each of the selected values as a new path metric when the determining means determines that it is small, and selects each of the subtracted results as a new path metric when the determining means determines no. Select as each path metric. As a result, it is possible to realize a Viterbi decoder that does not cause overflow and underflow and can operate at high speed with a simple circuit configuration.

[0018]

[0019]

The Viterbi decoder according to the second invention calculates each branch metric indicating the probability of transition from a possible data series to a data series including sampling data, and calculates each branch metric one sampling before. The data series that can be taken is the original data series Add each path metric that indicates the certainty, compare the values obtained by addition and select the value with the highest certainty, and select the value corresponding to each selected value. In a Viterbi decoder that estimates the most probable data sequence based on the data sequence, subtraction means for subtracting a first predetermined value from each of the selected values, and each path metric to each branch metric. Then, in parallel with the process of comparing the respective values obtained by the addition and selecting the value with high certainty, one of the above-mentioned respective path metrics becomes the second place. Determination means for determining less or not than the value, if it is determined that the determination means is small, the
Select each selected value as each new path metric,
When the judging means judges no, the subtracting means decreases.
A means for selecting each calculated result as a new path metric is provided.

In this Viterbi decoder, the values obtained by adding each branch metric and each path metric are compared with each other to select a value with high certainty. The means to subtract
The first predetermined value is subtracted from each of the selected values. on the other hand,
In parallel with the process of comparing each value obtained by adding each branch metric and each path metric to select a value with high certainty, the determining means determines that any one of the path metrics is higher than the second predetermined value. Determine if it is small. When the judging means judges that the selecting means is small, the selecting means
When each value is selected as a new path metric and the determination means determines that the result is no , each result subtracted by the subtraction means is selected as a new path metric. As a result, it is possible to realize a Viterbi decoder that does not cause overflow and underflow and can operate at high speed with a simple circuit configuration.

[0022]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to the drawings showing the embodiments thereof. Embodiment 1. FIG. 1 is a block diagram showing a configuration of an embodiment of a Viterbi decoder according to the first invention. The Viterbi decoder includes a branch metric calculation unit 10 that calculates a branch metric based on a sampling value y _t input by being converted into a digital signal by an A / D converter (not shown) and a given expected value. , Add-Comp to obtain path metric using branch metric
are-Select) circuit 11, path metric memory 13 for storing the obtained path metric, and path memory 12 for storing data corresponding to the obtained path metric and outputting finally determined data. Have.

The operation of the Viterbi decoder having such a configuration will be described below. The branch metric calculation unit 10
When the sampling value y _t is input, a branch metric calculation is executed, and the calculated branch metric is AC.
It is given to the S circuit 11. The ACS circuit 11 adds a branch metric to the path metric before one sampling given from the path metric memory 13, compares the path metrics after the addition two by two, and selects the smaller one. The selected path metric is stored in the path metric memory 13 as a new path metric. Further, the data corresponding to the selected path metric is supplied to the path memory 12, and the data corresponding to the surviving path in the path memory 12 is output as the finalized data.

FIG. 2 is a block diagram showing the configuration of the ACS circuit 11 of the Viterbi decoder according to the first invention. This A
The CS circuit 11 is suitable for a data sequence with a constraint length of 4, and the path metric memory 13 is provided with 16 types of branch metrics that are 7-bit bus signals input from a branch metric calculation unit (not shown). Adder 14 for adding the eight types of path metrics before sampling stored in 1., comparator 16 for comparing two path metrics after addition, and selection for selecting the smaller of the two path metrics And a container 15.

The ACS circuit 11 also includes a selector 15
Subtractor 17 for subtracting a predetermined value (first predetermined value; eg 128 (decimal)) from each path metric selected by
And a comparator 19 for determining whether or not any of the results subtracted by the subtractor 17 is smaller than a predetermined value (second predetermined value; for example, -256 (decimal)) and an OR gate 20 (determination And the comparator 19 and the OR gate 20 are small and outputs 1, the path metric selected by the selector 15 is selected as a new path metric and given to the path metric memory 13. When the comparator 19 and the OR gate 20 determine NO and output 0, the selector 18 selects each result subtracted by the subtractor 17 as a new path metric and gives it to the path metric memory 13. ing. Here, the predetermined value subtracted by the subtractor 17 is approximately -1/2 times the predetermined value serving as a reference for the comparator 19 and the OR gate 20 to determine.

Hereinafter, the ACS circuit 11 having such a configuration will be described.
Will be described with reference to the time chart of FIG. 3 showing it. When 16 branch metric signals, which are 7-bit bus signals, are input from the branch metric calculation unit (not shown), the adder 14 stores 8 branch metric values stored in the path metric memory 13 as branch metric values. Add the path metrics of the seeds (Fig. 3Ad
d). The comparator 16 compares the 16 path metrics after the addition two by two (Com.), And the selector 15
Selects the smaller of the two path metrics (Sel.).

The subtractor 17 subtracts a predetermined value (for example, 128 (decimal)) from each path metric selected by the selector 15 (Sub). The comparator 19 compares each result subtracted by the subtractor 17 with a predetermined value (for example, -256 (decimal)), and outputs 1 when each subtracted result is smaller (Com.). The OR gate 20 gives 1 to the selector 18 if at least one of the eight outputs of the comparator 19 is present (OR).

When 1 is given from the OR gate 20, the selector 18 selects each path metric selected by the selector 15 as a new path metric (Se).
l. ), And when 0 is given from the OR gate 20 to the path metric memory 13, each result subtracted by the subtractor 17 is selected as a new path metric (Se).
l. ), And gives it to the path metric memory 13. The path metric memory 13 stores each given new path metric (FF). As a result, the Viterbi decoder obtains the minimum value of each selected path metric in the related art, and compares the Viterbi decoder that subtracts the minimum value from each path metric with eight simultaneous 1's by the subtractor 17. Overflow and underflow can be prevented by the subtraction operation of eight times, one comparison operation of eight simultaneous operations by the comparator 19 and one OR operation, so that high-speed operation is possible and the circuit configuration is simple. Is.

FIG. 4 is a block diagram showing a detailed configuration example of the ACS circuit of the Viterbi decoder according to the first invention. In the ACS circuit, 16 samplings of branch metrics input from the calculation units BM _{0 to} BM ₁₅ of the branch metric calculation unit 10 are stored in each of the memory units PMM _{0 to} PMM ₇ of the path metric memory 13 by one sampling. The eight types of path metrics described above are compared with the addition units Add _{0 to} Add ₇ , Add _{8 to} A of the adder 14.
Add by dd ₁₅ . Each path metric after addition is
2 by the comparison units Com _{0 to} Com ₇ of the comparator 16.
The selection units Sel ₀ to
Sel ₇ selects the smaller one.

Each path metric selected by the selection units Sel _{0 to} Sel ₇ is given to the selection units Sel _{10 to} Sel ₁₇ of the selector 18, while being given a predetermined value by the subtraction units Sub _{0 to} Sub ₇ of the subtractor 17. (Eg 128 (decimal)) is subtracted. Subtraction unit Su
Each result subtracted by b _{0 to} Sub ₇ is a comparator 19
Is compared with a predetermined value (for example, −256 (decimal)) by the comparison units Com _{10 to} Com ₁₇ of the comparison unit C.
om _{10 to} Com ₁₇ output 1 when the respective subtracted results are smaller. The OR gate 20 is a comparison unit C.
Of the eight outputs from om _{10 to} Com ₁₇ , if there is at least one 1, select 1 to select unit Sel _{10 to} Sel of selector 18.
Give to ₁₇ .

Selection unit Sel _{10 to} Se of the selector 18
When 1 is given from the OR gate 20, l ₁₇ selects each result subtracted by the subtraction units Sub _{0 to} Sub ₇ as a new path metric, and the OR gate 2
When 0 to 0 is given, the selection unit Sel ₀ ~
Each path metric selected by Sel _{7 is} selected as a new path metric, and the path metric memory 1
3 memory units PMM _{0 to} PMM ₇ . The memory units MM _{0 to} PMM ₇ store each given new path metric. Further, the data corresponding to the new path metric is supplied to the path memory 12, and the data corresponding to the surviving path in the path memory 12 is
It is output as confirmed data.

Embodiment 2. FIG. 5 is a block diagram showing the configuration of the ACS circuit of the Viterbi decoder according to the present invention. This ACS circuit is suitable for a data series with a constraint length of 4, and has seventeen types of 7 types that are input from a branch metric calculation unit (not shown).
An adder 14 that adds eight types of path metrics stored in the path metric memory 13 before sampling to the branch metric that is a bit bus signal, and a comparator 16 that compares the path metrics after addition two by two. When,
The selector 15 selects the smaller one of the two path metrics.

This ACS circuit also performs parallel processing operations of the adder 14, the comparator 16 and the selector 15 described above, and stores the eight types of path metrics stored in the path metric memory 13 for one sampling before. A selector (selection means) 21 for selecting the minimum value and each path metric selected by the selector 15 are subtracted from the minimum value of the path metric selected by the selector 21, and each subtracted result is newly added to each path metric. And a subtractor 22 which is provided to the path metric memory 13. The configuration and operation of the Viterbi decoder according to the present invention are the same as the configuration and operation of the Viterbi decoder described in the first embodiment, so description thereof will be omitted.

The operation of the ACS circuit having such a configuration will be described below with reference to the time chart of FIG. 6 showing the operation. When 16 branch metric signals, which are 7-bit bus signals, are input from the branch metric calculation unit (not shown), the adder 14 stores 8 branch metric values stored in the path metric memory 13 as branch metric values. Add path metrics of seeds (Fig. 6Ad
d). The comparator 16 compares the 16 path metrics after the addition two by two (Com.), And the selector 15
Selects the smaller of the two path metrics (Sel.).

The selector 21 is a processing operation (Add, Com, S) of the adder 14, the comparator 16 and the selector 15 described above.
el. ), The minimum value of eight types of path metrics stored in the path metric memory 13 before one sampling is selected (Min.Sel.). Subtractor 22
Subtracts the minimum value of the path metric selected by the selector 21 (Min.Sel.) From each path metric selected by the selector 15 (Sel.) (Sub), and subtracts each result into a new path. It is given to the path metric memory 13 as a metric. The path metric memory 13 stores each given new path metric (FF).

As a result, this Viterbi decoder obtains the minimum value of each path metric one sampling before, instead of the conventional minimum value of each selected path metric, so that the processing operation for obtaining the minimum value is performed. , The adder 14, the comparator 16, and the selector 15 can be performed in parallel with each other, which enables high-speed operation and prevents overflow and underflow.

FIG. 7 shows A of the Viterbi decoder according to the present invention.
It is a block diagram which shows the detailed structural example of a CS circuit. In the ACS circuit, 16 samplings of branch metrics input from the calculation units BM _{0 to} BM ₁₅ of the branch metric calculation unit 10 are stored in each of the memory units PMM _{0 to} PMM ₇ of the path metric memory 13 by one sampling. The eight types of path metrics described above are compared with the addition units Add _{0 to} Add ₇ , Add _{8 to} A of the adder 14.
Add by dd ₁₅ . Each path metric after addition is compared two by two by the comparison units Com _{0 to} Com ₇ of the comparator 16, and the selection unit Sel of the selector 15 is compared.
The smaller one is selected from _{0 to} Sel ₇ .

The selector 21 is the addition unit described above.
To Add₀~ Add₇, Add₈~ Add₁₅, Comparison uni
At Com₀~ Com₇And selection unit Sel₀~ S
el ₇In parallel with the processing operation of the memory unit PMM₀
~ PMM₇8 kinds of one before sampling stored in
Select the minimum path metric. Subtraction of subtractor 22
Unit Sub₀~ Sub₇Is the selection unit Sel₀
~ Sel₇Selector 2 from each path metric selected by
1 subtracts the minimum value of the selected path metric and subtracts
Each result is set as a new path metric.
PMM₀~ PMM₇Give to. Memory unit PM
M₀~ PMM₇Gives each new path metric given
Remember. In addition, the data corresponding to the new path metric
Data is supplied to the path memory 12 and stored in the path memory 12.
The data corresponding to the survivor path in the
Output as data.

Embodiment 3. FIG. 8 is a block diagram showing the configuration of the ACS circuit of the Viterbi decoder according to the second invention. This ACS circuit is suitable for a data series having a constraint length of 4 and has 16 types of data input from a branch metric calculation unit (not shown).
An adder 14 for adding eight kinds of path metrics stored before 1 sampling stored in the path metric memory 13 to a branch metric which is a 7-bit bus signal, and a comparator for comparing the path metrics after addition two by two. 16
And a selector 15 for selecting the smaller one of the two path metrics, and a subtracter 25 for subtracting a predetermined value (first predetermined value; eg 64 (decimal)) from each path metric selected by the selector 15. It has and.

This ACS circuit also performs parallel processing operations of the adder 14, the comparator 16 and the selector 15 described above, and stores eight kinds of path metrics stored in the path metric memory 13 for one sampling before. A comparator 23 and an OR gate 24 for determining whether any of them is smaller than a predetermined value (second predetermined value; for example, -128 (decimal)).
When the (determination means) and the comparator 23 and the OR gate 24 determine that they are small and outputs 1, the path metric selected by the selector 15 is selected as a new path metric and given to the path metric memory 13. When the comparator 23 and the OR gate 24 determine that the output is 0 and output 0, the selector 2 selects each result subtracted by the subtractor 25 as a new path metric and supplies it to the path metric memory 13.
6 and.

Here, the predetermined value subtracted by the subtractor 25 is
It is approximately -1/2 times the predetermined value that serves as a reference for the comparator 23 and the OR gate 24 to make a determination. The configuration and operation of the Viterbi decoder according to the second aspect of the invention are the same as the configuration and operation of the Viterbi decoder described in the first embodiment, so description will be omitted.

The operation of the ACS circuit having such a configuration will be described below with reference to the time chart of FIG. 9 showing the operation. When 16 branch metric signals, which are 7-bit bus signals, are input from the branch metric calculation unit (not shown), the adder 14 stores 8 branch metric values stored in the path metric memory 13 as branch metric values. Add path metrics of seeds (Fig. 9Ad
d). The comparator 16 compares the 16 path metrics after the addition two by two (Com.), And the selector 15
Selects the smaller of the two path metrics (Sel.). The subtractor 25 subtracts a predetermined value (for example, 64 (decimal)) from each path metric selected by the selector 15 (Sub).

The comparator 23 and the OR gate 24 are stored in the path metric memory 13 in parallel with the processing operations (Add, Com, Sel.) Of the adder 14, the comparator 16 and the selector 15 described above. 8 before 1 sampling
Any of the path metrics of the seeds has a predetermined value (for example, -128).
(Decimal)) It is determined whether it is smaller than (Com, O
R).

When the selector 26 determines that the comparator 23 and the OR gate 24 are small and outputs "1", the selector 15
When each path metric selected by is selected as a new path metric and is given to the path metric memory 13, and when the comparator 23 and the OR gate 24 determine that there is no and output 0, the subtracter 25 subtracts each path metric. The result is selected as each new path metric (Sel.) And is given to the path metric memory 13. The path metric memory 13 stores each given new path metric (FF). As a result, this Viterbi decoder performs the operation of detecting the underflow in parallel with the processing operation of the adder 14, the comparator 16, and the selector 15, so that high-speed operation is possible and overflow and underflow are caused. Flow can be prevented.

FIGS. 10 and 11 are block diagrams showing detailed configuration examples of the ACS circuit of the Viterbi decoder according to the second invention. This ACS circuit includes a branch metric calculator 1
16 input from each calculation unit BM0 to BM15 of 0
For the branch metric of the street, the path metric memory 1
8 types of path metrics stored in the memory units PMM0 to PMM7 of No. 3 before one sampling are added to the addition units Add0 to Add7, A of the adder 14.
Add from dd8 to Add15. Each path metric after addition is used as a comparison unit Com0 to Com of the comparator 16.
7 are compared two by two, and the smaller one is selected by the selection units Sel0 to Sel7 of the selector 15.

The path metrics selected by the selection units Sel _{0 to} Sel ₇ are given to the selection units Sel _{10 to} Sel ₁₇ of the selector 26, while the subtraction units Sub _{0 to} Sub ₇ of the subtractor 25 give predetermined values. (Eg 64 (decimal)) is subtracted. The comparison units Com _{10 to} Com ₁₇ of the comparator 23 are the addition units A described above.
dd _{0 to} Add ₇ , Add _{8 to} Add ₁₅ , comparison units Com _{0 to} Com ₇ and selection units Sel _{0 to} Sel.
_In parallel with the processing operation of ₇ , the eight kinds of path metrics stored in the path metric memory 13 before one sampling are compared with a predetermined value (for example, -128 (decimal)),
When the path metric is smaller, 1 is output. OR
The gate 24 supplies 1 to the selection units Sel _{10 to} Sel ₁₇ if at least one of the eight outputs of the comparator 23 is 1.

The selection units Sel _{10 to} Sel ₁₇ are ORed.
When the gate 24 outputs 1, the selection unit Sel
Each path metric selected by _{0 to} Sel ₇ is selected as a new path metric, and the path metric memory 1 is selected.
When the OR gate 24 outputs 0, the subtraction units Sub _{0 to} Sub ₇ subtract each result as a new path metric and supply it to the path metric memory 13. The path metric memory 13 stores each given new path metric. Further, the data corresponding to the new path metric is supplied to the path memory 12, and the data corresponding to the surviving path in the path memory 12 is output as the finalized data.

[0048]

According to the Viterbi decoder according to the first and second inventions, overflow and underflow do not occur,
Moreover, a Viterbi decoder capable of high speed operation can be realized with a simple circuit configuration.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a Viterbi decoder according to the present invention.

FIG. 2 is a block diagram showing a configuration example of an ACS circuit of a Viterbi decoder according to the first invention.

FIG. 3 is a time chart showing the operation of the ACS circuit of the Viterbi decoder according to the first invention.

FIG. 4 is a block diagram showing a detailed configuration example of an ACS circuit of the Viterbi decoder according to the first invention.

FIG. 5 is a block diagram showing a configuration example of an ACS circuit of a Viterbi decoder according to the present invention.

FIG. 6 is a time chart showing the operation of the ACS circuit of the Viterbi decoder according to the present invention.

FIG. 7 is a block diagram showing a detailed configuration example of an ACS circuit of a Viterbi decoder according to the present invention.

FIG. 8 is a block diagram showing a configuration example of an ACS circuit of a Viterbi decoder according to the second invention.

FIG. 9 is a time chart showing the operation of the ACS circuit of the Viterbi decoder according to the second invention.

FIG. 10 is a block diagram showing a detailed configuration example of an ACS circuit of a Viterbi decoder according to the second invention.

FIG. 11 is a block diagram showing a detailed configuration example of an ACS circuit of a Viterbi decoder according to the second invention.

FIG. 12 is a chart showing an example of a data series.

FIG. 13 is a flowchart showing an operation of calculating a branch metric.

FIG. 14 is a block diagram showing a detailed configuration example of an ACS circuit of a conventional Viterbi decoder.

FIG. 15 is a block diagram showing a configuration example of a path memory.

FIG. 16 is a block diagram showing a configuration example of an ACS circuit of a conventional Viterbi decoder.

FIG. 17 is a time chart showing the operation of the ACS circuit of the conventional Viterbi decoder.

[Explanation of symbols]

10 Branch metric calculator 11 ACS circuit 12 pass memory 13 path metric memory 14 adder 15 selector 16, 19, 23 comparator 17,22,25 Subtractor 18,26 Selector 19 Comparator (determination means) 20 OR gate (means for judging) 21 Selector (selection means) 23 Comparator (determination means) 24 OR gate (determination means)

Continuation of the front page (56) Reference JP-A-8-195037 (JP, A) JP-A-8-180608 (JP, A) JP-A-4-280123 (JP, A) JP-A-6-6242 (JP , A) JP-A-7-66735 (JP, A) JP-A-7-66736 (JP, A) JP-A-8-8763 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB) Name) H03M 13/00 G06F 11/10 H04L 1/00

Claims (2)

(57) [Claims] 1. A branch metric indicating the probability of transition from a possible data series to a data series containing sampling data is calculated, and the calculated branch metric is the original data series with a possible data series one sampling before. Each path metric indicating the certainty is added, the values obtained by the addition are compared, the value with the highest certainty is selected, and the most probable data is based on each data series corresponding to each selected value. A Viterbi decoder for estimating a sequence, means for subtracting a first predetermined value from each of the selected values,
A means for determining whether or not any of the results subtracted by the means is smaller than a second predetermined value; and, when the means determines that the result is smaller, the selected values are selected as new path metrics. and, when said means determines that the negative, the reduced
A Viterbi decoder comprising means for selecting each calculated result as a new path metric. 2. A branch metric indicating the probability of transition from a possible data series to a data series containing sampling data is calculated, and the calculated branch metric is the original data series having a possible data series one sampling before. Each path metric indicating the certainty is added, the values obtained by the addition are compared, the value with the highest certainty is selected, and the most probable data is based on each data series corresponding to each selected value. In a Viterbi decoder for estimating a sequence, subtraction means for subtracting a first predetermined value from each selected value, and each path metric added to each branch metric, each value obtained by addition In parallel with the process of selecting a value with high probability, it is determined whether or not any of the path metrics is smaller than a second predetermined value. A constant means, when it is determined that the determination means is small, the
Select each selected value as each new path metric,
When the judging means judges no, the subtracting means decreases.
A Viterbi decoder comprising means for selecting each calculated result as a new path metric.