JPH0361374B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] Based on the node number and the contents of the path memory corresponding to this node number, the node number of the side selected as a survivor with this node number is repeatedly determined, and finally, A Viterbi decoder that uses a path tracing method to obtain a decoded output from the reached node number is equipped with a path trace control unit that terminates tracing at a node number that matches the node number one decoding cycle before. , unless the error rate becomes extremely bad, the node numbers will match in about two or less traces, and the decoding speed can be improved.

[Industrial application field]

The present invention relates to a Viterbi decoder that uses a path tracing method.

The Viterbi decoder is used for maximum likelihood decoding of convolutional codes, and selects the path with the closest code distance to the received code sequence as the maximum likelihood path from among multiple known code sequences. death,
Decoded data is obtained in accordance with this selected path, and because it has a high error correction ability, it is used as a decoder for satellite communications and the like.

[Conventional technology]

The Viterbi decoder is composed of a distributor, an ACS circuit, and a path memory as the main elements, and the ACS circuit is
It consists of an adder, a comparator, and a selector. The distributor calculates a branch metric from the received code of the demodulated output of the receiving device, and the branch metric is added to the ACS circuit and added to the path metric of one symbol before, and the addition result becomes a new path metric. , by comparing these path metrics, the smaller path metric is determined as the path metric of the most likely path, and the path metric and path select signal are output. The path memory stores the history of the most likely path by applying a path select signal from the ACS circuit.It is composed of a selector and a flip-flop, and has a structure in which path memory cells are connected in multiple stages, or a random access memory is used. It will be done.

In such a Viterbi decoder, the larger the code constraint length, the greater the error correction ability, but since the circuit size increases exponentially, it is usually about 3 to 7 times. A restraint length is used.

For example, when the coding rate of the received code is 1/2 and the constraint length is 4, if the received code is judged by 8-level soft decision, the demodulated output signals I and Q of the orthogonal modulation signal are
Each output has a 3-bit configuration, and a total of 6 bits are input to the distributor. The distributor calculates branch metrics as described above, and calculates (I+Q), (I+), (+Q), (+
)
Four types of branch metrics of 4-bit configuration indicating 1 to 14 are output.

Also, the ACS circuit has 2 ^K-1 pieces, where the constraint length is K.
It is composed of ACS sections, and when K=4, it is composed of eight ACS sections.
In each ACS unit, an adder adds this branch metric and the path metric one symbol before to create a new path metric, and a comparator outputs a path select signal for comparing the new path metrics and selecting the smaller one. The selector is controlled by the path select signal to output path metrics. In this case, since the path metric gradually increases in value, when a certain threshold is reached, normalization processing is performed to prevent the calculation result from overflowing.

The path select signals output from each of the eight ACS units are added to the path memory, the history of the most likely path is stored, and the contents of the path memory of the history with the minimum path metric become the decoded output.

FIG. 14 shows a block diagram of a conventional path memory, taking as an example the case where the constraint length K=3. In the same figure, 41-44 are ACS department, MS
11 to MS43 are path memory cells. Although only three stages of this path memory are shown, the number of stages approximately five or six times the constraint length is normally used. Also, the path memory cell MSij (i, j=1, 2, 3,...)
As shown in the enlarged view below, each includes a selector 44 and a flip-flop 45. The selector 44 is selectively operated by the path select signal from the ACS section, and its selection output is applied to the data terminal D of the flip-flop 45. A clock signal is applied to the clock terminal CK.
An output signal from output terminal Q is applied to two pass memory cells in the next stage.

First stage path memory cells MS11, MS21, MS
31 and MS41, "0", "1", "0", and "1" are respectively added as initial stage inputs, and are shifted so as to sequentially transition the internal state in response to the path select signal. That is, in each decoding cycle, the contents of the path memory cell on the side determined to be the surviving path by the ACS units 41 to 44 are transferred using the path select signal.

Further, FIG. 15 shows a conventional path memory configured using random access memory (RAM), in which 51 is a first stage input setting section, 52,
53 is a random access memory (RAM), AD is an address input terminal, DI is a data input terminal, DO is a data output terminal, and 54 is an output processing unit including a majority circuit and the like.

This path memory is multiplexed using two memories, and for example, a certain node number I corresponding to a certain path memory cell of the above-mentioned path memory
At the address of memory 52, 〓I/2''
and 2 ^K-1 +〓I/2'', and set the node number of the one selected as the survivor, and also set the memory 5.
Set I to address 3 and connect the data output terminal DO of memory 52 to the data input terminal of memory 53.
Transfer data (path information) to DI. This is performed for all nodes, and the decoded output is derived from the output processing unit 54. In the next decoding cycle, memory 5
Data (path information) is transferred from the data output terminal DO of No. 3 to the data input terminal DI of the memory 52.
Note that the above-mentioned 〓I/2'' is a Gaussian symbol indicating the largest integer not exceeding I/2.

Furthermore, a path tracing method has been proposed in which the most likely path is determined by tracing path selection information stored in a path memory. This path tracing method is
From the node number and the contents of the path memory corresponding to that node number, find the node number of the side selected as the survivor in that node, repeat this process, and calculate from the node number when the end of the path memory is reached. This is a method to obtain decoded output.

[Problem that the invention seeks to solve]

In the conventional example shown in FIG. 14, the path memory cell has a structure consisting of a selector 44 and a flip-flop 45, so it has the disadvantage that it is difficult to integrate it into an integrated circuit like a random access memory. .

In the conventional example shown in FIG. 15, it is possible to construct an integrated circuit path memory by using a random access memory, but since it is multiplexed, for example, a decoder with a constraint length of 7 cannot be used. When configuring the memory 52,
53 needs to be accessed 64 times. Therefore, there is a drawback that it is difficult to improve the decoding processing speed. It is also possible to reduce the number of accesses by lowering the degree of multiplicity, but in that case the number of memories will increase.

Furthermore, in the conventional path tracing method described above, the maximum likelihood path is traced by repeating node number calculations corresponding to the number of stages in the path memory, which increases the number of accesses to the path memory and slows down the decoding process. The disadvantage is that it is difficult to increase the speed.

The present invention aims to improve the decoding processing speed by reducing the number of accesses to memory per decoding cycle.

[Means for solving problems]

The Viterbi decoder of the present invention applies a path tracing method to reduce the number of accesses to the path memory, and will be explained with reference to FIG.

A divider 1 that calculates a branch metric from the received code, adds the branch metric from this divider 1 and the path metric one symbol before, and selects the maximum likelihood path by comparing the new path metric of the addition output and this path metric. an ACS circuit 2 that outputs a path select signal for performing a path select signal, a path memory 3 that stores the path select signal, a trace memory 5 that stores a traced node number, and the read contents of the path memory 3 that correspond to the node number. and its node number, the node number of the node selected as a survivor in that node is repeatedly determined, and the trace is aborted when it matches the node number stored in the trace memory 5 one decoding cycle before. The decoded output is derived from the path trace control section 4.

[Effect]

There is a high probability that the maximum likelihood path in a certain decoding cycle is almost the same as the maximum likelihood path in the previous decoding cycle. Therefore, if the node number is stored in the trace memory 5 and the node number obtained during tracing matches the node number one decoding cycle before, the subsequent node numbers will match. Tracing can be stopped when a match is reached. That is, by not tracing to the end, it is possible to reduce the number of accesses to the path memory, and it is possible to improve the decoding processing speed.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 2 is a block diagram of an embodiment of the present invention,
11 is a distributor, 12 is an ACS circuit, 13 is a minimum path metric detection circuit, 14 is a timing generation circuit, 15 is a path trace control section, 16 is a path memory, 17 is a trace memory, 18 is a trace state control circuit, and 19 is a multiplexer. (MPX),
20 is a node number calculation section, 21 is a comparison section, 22 is a pointer control section, 23 is a trace address counter, 24 and 26 are address control sections, and 25 and 27 are data control sections. Timing generation circuit 14
The circuit outputs a clock signal and a timing signal to be supplied to each section using a high-speed clock signal and a data clock signal. Further, the distributor 11 calculates a branch metric from the received code a and adds this branch metric b to the ACS circuit 12.

The ACS circuit 12 includes a number of adders, comparators, and selectors corresponding to the constraint length K of the received code a, operates in accordance with the timing signal c from the timing generation circuit 14, and generates branch metrics b and one symbol. Add the previous path metric with the adder, compare the new path metric of the addition output with the comparator, output the smaller path metric from the selector, add the path metric e to the minimum path metric detection circuit 13, and add it to the comparator. A path select signal d indicating the comparison result is applied to the multiplexer 19 and the node number calculation section 20. The trace state control circuit 18 operates according to the timing signal from the timing generation circuit 14 and switches the trace state according to the coincidence detection signal i from the comparator 21.

Further, the pointer control unit 22 shifts the pointer indicating the start address of the path memory 16 and the trace memory 17 by one stage for each decoding cycle, thereby causing the trace address counter 23 to shift by one stage.
The address signal during tracing is output from. A control signal j such as a write enable signal and a read enable signal and an address signal k are applied from the address control unit 24 to the path memory 16, and read data l from the path memory 16 is transferred to the data control unit 25. Also, write data l is added to the path memory 16 via the data control section 25. Further, control signals m such as a write enable signal and a read enable signal are sent from the address control unit 26 to the trace memory 17.
and address signal n are added to the data control unit 2.
Data (node number) o is transferred between 7 and the trace memory 17. Read node number h
is applied to the comparison unit 21 via the data control unit 27 and compared with the node number g calculated by the node number calculation unit 20, and the comparison match signal i is applied to the trace state control circuit 18.

The process of inputting the received code a and writing the path select signal to the path memory 16 is the same as in the conventional example. The path memory 16 and the trace memory 17 are constituted by ordinary random access memories, and as shown in FIG. 3, the start addresses of the path memory 16 and the trace memory 17 are designated by pointers.

This pointer is controlled by the pointer control unit 22 and is shifted by one stage in the pointer advancing direction every decoding cycle. A path select signal and a start node number are added to the start address indicated by the pointers in the path memory 16 and trace memory 17. The trace direction is the opposite direction to the pointer advancement direction, starts from the first address indicated by the pointer, and traces the path select signal and node number in the previous decoding cycle according to the address signal from the trace address counter. is read out. The physical addresses of the path memory 16 and the trace memory 17 are the sum of the trace logical address and the start address determined by the pointer, modulo the path memory length. Therefore, it is desirable that the path memory length be 2 ⁿ stages.

FIG. 4 is an explanatory diagram of path tracing, in which tracing can be started by selecting any node among the nodes with node numbers 0 to 7 (when constraint length K=4). Path metric minimum nodes are preferred. In FIG. 4, node number 7, which has the smallest path metric value of 62 among 82, 78, 76, 64, and 62, is selected as the trace start node.

Trace start node number N ₀₀ , this node number
If the contents of the path memory 16 corresponding to N ₀₀ are SP ₀₀ , then at this point the ACS corresponding to node number N ₀₀
Circuit 12 means that the transition from node number N ₀₁ to N ₀₁ = 2 ^K-2 ×PS ₀₀ +N ₀₀ /〓2''...(1) is selected as the survival path, and the next step is to The path select signal PS ₀₁ of the contents of the path memory 16 corresponding to the node number N ₀₁ is read. Such operations are repeated. Note that 〓N ₀₀ /2'' means the largest integer not exceeding N ₀₀ /2, as described above.

In FIG. 4, in step 1, the node number calculation unit 20 selects the minimum path metric node number N ₀₀ =7 and the latest path select signal SP ₀₀ "1" as the corresponding contents of the path memory 16.
is read into , the calculation according to formula (1) is performed, and 4×
Since 1+3=7, the node number N ₀₁ =7 is calculated.

In the next step 2, "1" of the path select signal SP ₀₁ of the contents of the path memory 16 corresponding to this node number N ₀₁ =7 is read out, and the node number N ₀₂ =
7 is calculated. The next step 3 is the node number
"0" of the path select signal SP ₀₂ of the contents of the path memory 16 corresponding to N ₀₂ is read out, and the node number N ₀₃ =3 is calculated. Similarly, in step 8, the node number N ₀₈ =4 is calculated. If this node number N ₀₈ = 4 is the last trace,
Since 4="100", the LSB (least significant bit) of "0" becomes the decoded output. Then, the node numbers in steps 1 to 8 are written into the trace memory 17 for each step.

Generally, in a Viterbi decoder, there is a high probability that the maximum likelihood path obtained in a certain decoding cycle is almost the same as the maximum likelihood path in the previous decoding cycle. In other words, there is a high probability that it will be the same as the maximum likelihood path in the previous decoding cycle shifted by one stage and one transition added to it.

FIG. 5 is an explanatory diagram of a path trace, showing a path trace in a decoding cycle following the decoding cycle of FIG. 4. The contents of the path memory are
By adding the latest path select signal to the beginning, the contents shown in FIG. 4 are shifted by one stage. Also, the path metric value in this decoding cycle is the minimum 0 among 19, 18, 14, 5, and 0.
The trace starts from node number 1. Fourth
If you calculate the node number in the same way as shown in the figure, step 1~
8, N ₀₀ = 0, N ₀₁ = 4, N ₀₂ = 6, N ₀₃
=7, _N04 =3, _N05 =1, _N06 =0, _N07 =0,
N ₀₈ =0. And the last node number N ₀₈
= 0, the LSB "0" is the decoded output.

Each node number is written to the trace memory 17, but when compared with the contents of the trace memory shifted by one stage in the previous decoding cycle, 3
The node number 7 will match on the second occasion, and all subsequent node numbers will be the same. That is, when the node number in the previous decoding cycle and the node number in the current decoding cycle match, the subsequent trace is discontinued and the trace is traced one step before the last node number in the previous decoding cycle. The decoding output can be obtained by using the node number as the last node number of the trace in the current decoding cycle.

In such a tracing process, the comparison unit 21 compares the node number g calculated by the node number calculation unit 20 and the node number h in the previous decoding cycle read from the trace memory 17, and if they do not match, writes the calculated node number g to the trace memory 17, and when the node numbers g and h match, a signal i is applied to the trace state control circuit 18 to abort the trace and move to the next control state. .

Figure 6 shows the number of traces, where the horizontal axis is Es/No (signal-to-noise ratio) and the vertical axis is the average trace for received codes with coding rate 1/2, constraint length 7, and 8-level soft decision. Let the physical length of the path memory be 32
The average number of traces when there are 48 stages, 48 stages, and 64 stages are shown by curves a, b, and c, respectively. Note that BER (bit error rate) indicates the value of bit errors after decoding when the physical length of the path memory is 8 stages. As can be seen from this curve diagram, the average number of traces is
Unless the line error rate becomes extremely bad, it will be 2 times or less.

FIG. 7 shows an operation time chart of path tracing, in which the number of traces per decoding cycle is set to 2. Therefore, the decoding cycle is
It is divided into a state, a trace state 1, and a trace state 2. Also, when the constraint length K = 7, the path select signal from the ACS circuit is
The case is shown in which the data is 64 bits and is written to the path memory four times every 16 bits. Therefore, the path memory requires two 8-bit/word random access memories.

A path select signal PS ₀₀ and a trace start node number N ₀₀ are output from the ACS circuit, and as described above, the path select signal PS ₀₀ is written in 4 times, each with 16 bits, as shown by the arrows. The latter two times are written in the I/O state. Also, in this I/O state, the decoded output (LSB of the last node number in the trace) is read from the trace memory, and then the trace start node number _N00 is written into the trace memory. Further, the node number N ₀₁ is calculated based on the above-mentioned equation (1) using the trace start node number N ₀₀ and the path select signal PS ₀₀ .

Referring to FIG. 2, the path select signal d is output from the ACS circuit 12, the trace start node number f is output from the minimum path metric detection circuit 13, and the node number calculation unit 20 selects the node based on equation (1). A number g is calculated. Further, the path select signal d is applied from the multiplexer 19 to the path memory 16 via the data control section 25 as write data l. At this time, since the start address of the path memory 16 and trace memory 17 is specified by the pointer by the pointer control unit 22, the 64-bit path select signal is sent to that address in four 16-bit blocks. written. Further, the trace start node number f is added to the trace memory 17 from the node number calculator 20 via the data control section 27.

When the node number N ₀₁ is calculated, the corresponding path select signal PS ₀₁ is set to trace state 1.
At this point, the node number N ₀₁ ' of the previous trace result is read out from the trace memory. In this case, the address signal from the trace address counter 23 controlled by the trace state control circuit 18 is applied to the path memory 16 and the trace memory 17 via the address control units 24 and 26, respectively, and the path select signal is and the node number are read out.

Then, _the node number N 02 is calculated based on the previously calculated node number N ₀₁ and the read path select signal PS ₀₁ , and during that time, the node number N ₀₁ ,
A comparison of N ₀₁ ′ is performed. In this process, the comparison unit 21 compares the node number g calculated by the node number calculation unit 20 and the node number h read from the trace memory 17, and if they match,
Since the signal i is applied to the trace state control circuit 18, a transition is made to the next control state. and,
The next decoding cycle is trace start node number
Conducted from _N10 .

If the comparison does not match, tracing is further continued. That is, the path select signal PS ₀₂ corresponding to the calculated node number N ₀₂ is set to trace state 2.
The node number is read from the path memory at
N ₀₃ is calculated, and the node number N ₀₂ ' of the previous trace result read from the trace memory is compared with the calculated node number N ₀₂ . If the comparison is a match, the process is performed from the next trace start node number _N10 , and the above-described operation is repeated.

Although FIG. 7 shows a case where tracing ends in one decoding cycle, FIG. 8 shows a case where tracing does not end. Trace start node number
The node numbers _{N 01 ,} N ₀₂ , N ₀₃ are calculated sequentially from N 00, and when the node numbers are compared in trace state 2, the node number N ₀₂ and the node number
If N ₀₂ ′ does not match, tracing will continue in the next decoding cycle. In that case, tracing is prohibited in the I/O state of the next decoding cycle, reading the decoding output, writing the trace start node number N ₁₀ , and passing the path select signal PS ₁₀ .
The latter half of the process is written. Then, in the next trace state 1, the path select signal PS ₀₃ corresponding to the node number N ₀₃ is read out, the previous node number N ₀₃ ' is read out, and in the next trace state 2, the node number N ₀₃ is read out. , N ₀₃ ′ are compared.

In this way, when tracing does not end in one decoding cycle, there are three possible restart methods for starting the next trace in the decoding cycle where tracing has ended. FIGS. 9a to 9c are explanatory diagrams for restarting path traces, and if the starting node numbers of the trace in decoding cycles 0, 1, 2, ... are N ₀₀ , N ₁₀ , N ₂₀ , ..., the restart method 1, as shown in a, restarts from the trace start node selected in the next decoding cycle of the decoding cycle in which the previous trace (trace that did not end in one decoding cycle) was started, and decoding cycle 0 Suppose that tracing is performed from trace start node number N ₀₀ in decoding cycle 2 and ends in decoding cycle 2, then the next trace starts from trace start node number N ₁₀ selected in decoding cycle 1,
In this case, when the trace ends in one decoding cycle, the next decoding cycle 2 starts from the selected trace start node number _N20 .

Also, restart method 2, as shown in b, restarts from the trace start node in the decoding cycle where the previous trace ended (or the next decoding cycle), and as in the above case, the decoding cycle Trace is performed from the selected trace start node number N ₀₀ at 0, and decoding cycles 0 to 2
When the trace start node numbers N ₁₀ and N ₂₀ selected in decoding cycles 1 and 2 are written to the trace memory in the I/O state, and in the next decoding cycle 3, The trace is started from the trace start node number _N30 selected by the user.

In restart method 3, the trace is restarted from the trace start node in the decoding cycle where the previous trace ended (or the next decoding cycle). However, in the decoding cycle where the previous trace has not finished,
When writing to the trace memory in the I/O state, a dummy number is written instead of the trace start node number. Similarly to the above case, when the trace started from the trace start node number N ₀₀ ends in three decoding cycles of decoding cycles 0 to 2, the trace start node number N ₁₀ selected in decoding cycles 1 and 2 , instead of N ₂₀ ,
A dummy number indicating a non-existent node number is
In the O state, data is written to the trace memory, and in the next decoding cycle 3, tracing is started from the selected trace start node number _N30 . If this trace also does not end in one decoding cycle, a dummy number is written in the trace memory instead of the trace start node number N ₄₀ selected in the next decoding cycle 4, and the decoding cycle at the end of the trace or the next The trace will be started from the selected trace start node in the decoding cycle.

The above-mentioned restart method 1 has a somewhat complicated configuration due to the storage of the trace start node number and path select signal. Furthermore, when Es/No (signal-to-noise ratio) is degraded, the effective length of the path memory becomes shorter, so BER (bit error rate) deteriorates to some extent.
For example, in the case of coding rate 1/2, constraint length 7, 8-level soft decision, and path memory physical length 40 stages, Es/No=
At −0.5dB, BER=4.7×10 ^-3 . In addition, if the effective length of the path memory is 40 stages, BER = 2.5 ×
10 ^-3 .

Furthermore, restart method 2 has the simplest configuration. However, unlike restart method 1, it does not perform complete path tracing, so if Es/No is bad,
BER deterioration becomes relatively large.

Furthermore, restart method 3 has a somewhat more complicated configuration than restart method 2, and the number of traces increases. However, the BER is improved compared to restart method 2.

Figure 10 shows the error rate characteristics for restart method 2, where the horizontal axis is Es/No (signal-to-noise ratio) and the vertical axis is BER (bit error rate). The case is shown when the length is 7 and the path memory physical length is 64 stages. In the figure, curve a shows the relationship between Es/No and BER without error correction,
Also, curve b has an average number of traces of 2, and curve c has an average of 8 traces.
curve d shows 16 times, curve e shows 32 times, and curve f shows the theoretical bit error rate.

In addition, Fig. 11 shows the error rate characteristics for restart method 3. Under the same conditions as in Fig. 10, curve A shows the case without error correction, similar to curve a in Fig. 10. Curve B shows the theoretical bit error rate, similar to curve f in FIG. 10, when the average number of traces is 2 times/decoding cycle. That is, in the case of restart method 3, by setting the average number of traces to 2 times/decoding cycle, it is possible to obtain error rate characteristics close to the theoretical value.

Furthermore, Fig. 12 shows the error rate characteristics with respect to the average number of traces of restart method 3 under the same conditions as in Figs. 10 and 11, and curve a shows the theoretical bit error rate when Es/No is -0.5 dB. , curve b is Es/No
is +0.5 dB theoretical bit error rate, curves c, d, e
The physical length of the path memory is 16, 32, and 64, respectively.
Curves f and g show cases where the physical length of the path memory is 32 stages and 64 stages, respectively. It can be seen that when the physical length of the path memory is 64 stages, the BER hardly changes even if the average number of traces is set to 2 or more. That is, if the physical length of the path memory in this case is 64 stages, it can be seen that the number of times of tracing can be set to two.

FIG. 13 is a block diagram in the case of integrating the circuit, and the same reference numerals as in FIG. 2 indicate the same parts.
29 is a metric memory, 29 is a normalization circuit, 30 is a selector, 31 is a delay circuit, and 32 is a re-encoding correlator. Also, CS is the coding rule switching signal, DE is the data enable signal, IH is the metric calculation prohibition signal,
I and Q are reception codes, I/Q are selection signals for reception codes I and Q, CLK is a data clock signal, HCK is a high-speed clock signal, MD is mode setting information, RS is a reset signal, SYN is synchronous output information, DLC is a delay code output, and PEP is a pseudo error pulse output.

The path memory 16 and the trace memory 17 are constituted by a random access memory which is an integrated circuit, and the other configurations within the dashed line are constituted by one integrated circuit, and the metric memory 28 is shown in FIG. is included in the ACS circuit 12. The normalization circuit 29 normalizes the path metric so that it falls within a predetermined range, since the path metric gradually increases and overflows during addition processing or the like.

Further, the re-encoding correlator 32 re-encodes the decoded output from the path trace control unit 15 according to the code generation polynomial setting information, and selects the received codes I and Q using the selector 30 according to the selection signal I/Q. , and the delay output from the delay circuit 31 according to the path memory length setting information. If they match, there is no error, and
Since a pseudo error pulse PEP is output in the case of a mismatch, the error rate can be determined by counting this pseudo error pulse PEP within a certain period of time.

〔Effect of the invention〕

As explained above, in the present invention, the maximum likelihood path in a certain decoding cycle is almost the same as the maximum likelihood path in the previous decoding cycle. The number is stored, and the path trace control unit 4 calculates the node number of the node selected as the survivor in the node with the node number from the node number and the corresponding read contents of the path memory 3. The node number is compared with the node number stored in the trace memory 5 one decoding cycle before, and when they match, the trace is aborted.The decoding process can be performed with the average number of traces set to 2. This has the advantage of making it possible to speed up the process.

[Brief explanation of drawings]

Figure 1 is a block diagram of the principle of the present invention, Figure 2 is a block diagram of an embodiment of the present invention, Figure 3 is an illustration of address control, Figures 4 and 5 are diagrams of path tracing, and Figure 6 is an illustration of path tracing. Trace number curve diagram, Figures 7 and 8 are path trace operation time charts, Figure 9
Figures a to c are explanatory diagrams for restarting path tracing, Figures 10 to 12 are error rate characteristic curve diagrams, Figure 13 is a block diagram of integrated circuit implementation of the embodiment of the present invention, and Figures 14 and 15 are This is a conventional path memory. 1 is a distributor, 2 is an ACS circuit, 3 is a path memory,
4 is a path trace control unit, 5 is a trace memory,
11 is a distributor, 12 is an ACS circuit, 13 is a minimum path metric detection circuit, 14 is a timing generation circuit, 15 is a path trace control section, 16 is a path memory, 17 is a trace memory, 18 is a trace state control circuit, and 19 is a multiplexer. , 20 is a node number calculation section, 21 is a comparison section, 22 is a pointer control section, and 23 is a trace address counter.

Claims (1)

[Claims] 1. A distributor 1 that calculates a branch metric from the received code, adds the branch metric from the distributor 1 and the path metric one symbol before, and compares the path metric of the addition output and the path metric. an ACS circuit 2 that outputs a path select signal indicating maximum likelihood path selection according to the method; and a path memory 3 that stores the path select signal.
, a trace memory 4 that stores the node number that has been traced, and the node number of the side selected as a survivor with the node number, based on the node number and the read contents of the path memory 3 corresponding to the node number. The Viterbi decoder is characterized by comprising a path trace control unit 5 which repeatedly repeats this process and terminates the trace when the node number matches the node number stored in the trace memory 4 one decoding cycle before.