JPH0361377B2 - - Google Patents

Description

[Detailed description of the invention] [Table of contents] Overview Industrial field of application Prior art (Figures 9 to 12) Problems to be solved by the invention Means for solving the problems (Figure 1) Effect (Fig. 2) Configuration of the device according to the embodiment (Fig. 3, Fig. 4) Explanation of path tracing (Fig. 2, Fig. 5 to Fig. 7) Explanation of restart method of path tracing (Fig. 8) Effects of the invention [Summary] The maximum likelihood path is traced by repeatedly determining the node number of the side selected as the survivor with the node number using the node number and the contents of the path memory corresponding to the node number. A path tracing Viterbi decoder that outputs the most significant digit of the binary number of the node number reached as the decoded output.

[Industrial application field]

The present invention relates to a path tracing Viterbi decoder.

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. It obtains decoded data corresponding to the path that has been sent, and because of its high error correction ability, it is used as a decoder for satellite communications and other applications.

[Conventional technology]

The Viterbi decoder is constructed with a distributor, an ACS circuit, and a path memory as its main elements. FIG. 9 shows an example of a Viterbi decoder with constraint length K=3. In the figure,
1 is a distributor, 2 is an ACS section, and 3 is a path memory. This distributor 1 has orthogonal modulated decoded signals I and Q.
is input as a received code, and the distributor 1 calculates a branch metric for each node from this received code, and sends the branch metric to the ACS unit 2.
give to

The ACS unit 2 includes ACS circuits 2(0) to 2(3) corresponding to the nodes when the code generated by the encoder is expressed in a grid as shown in FIG.
Each of the ACSs 2(0) to 2(3) includes an adder, a comparator, and a selector. each
In addition to the branch metric values from the distributor 1, the ACS circuits 2(0) to 2(3) receive branch metric values from other ACS circuits corresponding to the two paths that can be selected by the nodes in the grid representation in FIG. The path metric values for each are input. ACS circuit 2(0)~2
(3) sets the input branch metric value to 1
The pathmetric values before the symbol are added to calculate new pathmetric values corresponding to the two paths, these pathmetric values are compared by a comparator, the one with the smaller pathmetric value is selected as the surviving path, and the selected path is A path selection signal indicating the path selection signal and the selected path metric value are output.

The path memory 3 receives the path selection signal from the ACS unit 2 and stores the history of the surviving paths, and the contents of the path memory of the history with the minimum path metric value are the decoded output. This path memory 3 can have a structure in which path memory cells each consisting of a selector and a flip-flop are connected in multiple stages, or a structure using a RAM.

FIG. 11 shows a block diagram of a conventional path memory when the constraint length K=3. In the same figure, 2
(0) to 2(3) are ACS circuits, and ACS circuit 2
(0) to 2(3) and MS11 to MS43 are path memory cells. Although only three stages of path memory are shown in the figure, the number of stages approximately five or six times the constraint length is normally used. In addition, the path memory cell MSij (i, j
= 1, 2, 3...) as shown in the enlarged view below.
Each of them is composed of a selector 44 and a flip-flop 45. The selector 44 performs a selection operation in response to a path selection signal from the ACS circuit, and provides its selection output to the data terminal D of the flip-flop 45. The output signal from the output terminal Q of the flip-flop 45 is supplied to two pass memory cells in the next stage.

First stage path memory cells MS11, MS21, MS
31. “0”, “1”, “0”, and “1” are applied to the MS41 as initial stage inputs, and are shifted so as to sequentially transition the internal state in response to the path selection signal. . That is, in each decoding cycle, the contents of the path memory cell on the side determined to be a surviving path by the ACS circuits 2(0) to 2(3) are transferred to the path memory cell on the other side using the path selection signal.

Figure 12 shows random access memory (RAM)
1 is a block diagram showing a conventional example in which a path memory is configured using a path memory. In the figure, 51 is a first-stage input setting section, 52 and 53 are RAMs, AD is an address input terminal, DI is a data input terminal, DO is a data output terminal, and 54 is an output processing section consisting of a majority circuit and the like.

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

[Problem that the invention seeks to solve]

When the path memory is constructed of path memory cells consisting of a selector 44 and a flip-flop 45 as shown in FIG. 11, it is difficult to achieve high integration like a RAM. In addition, as shown in Figure 12, if the path memory is configured with RAM, it is possible to highly integrate the path memory, but since the RAM is multiplexed, the number of accesses to RAM increases, and the decoding processing speed increases. It is difficult to improve For example, in the case of a decoder with constraint length K=7, it is necessary to access the memories 52 and 53 64 times per one decoding cycle. Although it is possible to reduce the number of access circuits by lowering the multiplicity, in that case the number of memories increases.

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide a Viterbi decoder using a path tracing method that can improve decoding processing speed while using a RAM that can be easily integrated.

[Means for solving problems]

FIG. 1 is a basic block diagram of a Viterbi decoder according to the present invention.

The Viterbi decoder according to the present invention includes a distributor 1 that calculates a branch metric value for each node from a received code, and a plurality of ACS circuits 2(0) to 2(n) provided for each node. In the ACS section 2, each ACS circuit 2(0) to 2(n) is
Path metric values are computed for two paths that can be selected based on the branch metric values from the distributor 1, and the computed results are compared to select a surviving path from the two paths, and path selection indicates the selection of the surviving path. A path memory 3 that outputs signals PS(0) to PS(n), a path memory 3 that stores path selection signals PS(0) to PS(n) in a predetermined number of stages corresponding to each node, and a node number N(0) of an arbitrary node. )~N(n)
Path trace control that repeats over a predetermined number of stages the calculation of the node number of the node selected as a survivor in the previous stage based on the path selection signals PS(0) to PS(n) of the path memory 3 corresponding to the node number. The trace memory 5 stores node numbers traced by the path trace control unit 4 over a predetermined number of stages. The most significant binary digit of the node number at a predetermined stage in the trace memory 5 is used as the decoded output.

When the constraint length is K, the ACS section 2 consists of 2K ^-1 circuits. For example, when K=4, the ACS section 2 consists of eight ACS circuits 2(0) to 2(7), each of which
ACS circuits 2(0) to 2(7) correspond to eight nodes, respectively. The eight nodes are assigned node numbers from 0 to 7, respectively. each
Path selection signals PS(0) to PS(7) are applied to the path trace control unit 4 from the ACS circuits 2(0) to 2(7).

It is also possible to include a minimum pathmetric detection circuit that detects the minimum pathmetric value from among the pathmetric values PM(0) to PM(7) calculated by the ACS circuits 2(0) to 2(7). In this case, the node number of the node corresponding to the detected minimum path metric value is sent to the path trace control unit 4.

[Effect]

The path tracing operation by the Viterbi decoder of the present invention will be explained below with reference to FIG.

Figure 2 is an explanatory diagram of path trace operation, and the diagram includes the node numbers 0 to 7 of each node (and their binary representation), the path metric value at that node number, and the path memory corresponding to that node number. Each path selection signal is depicted. The number of stages of the path memory is 5, which is the constraint length (K = 4 in this case).
Although it is desirable to have about 6 times as much, only 8 stages are shown in FIG. 2 to simplify the explanation.

First, the ACS circuits 2(0) to 2(7) operate in the same way as those of a normal Viterbi decoder to select a surviving path by performing path metric calculations and comparing the calculation results, and pass selection signals PS(0) to PS. (7)
(“0” or “1”). These path selection signals PS(0) to PS(7) are written into the path memory. In this case, this path selection signal corresponds to the most significant bit (MSB) of the node number (in binary notation) selected as the survivor.

The path trace control unit 4 first selects a node to start tracing and starts tracing. Although any node can be selected as the trace start node, preferably the node with the minimum path metric value is selected. In Figure 2,
The 62 nodes (node number 7) with the minimum path metric values 82, 78, 76, 64, and 62 are selected as the trace start nodes.

Now let the node number of the trace start node be N ₀ ,
(N ₀ = 0 to 2 ^K-1 −1, K is the constraint length, coding rate R =
1/2), and the contents of the path memory corresponding to this node number _N0 are assumed to be _PS0 . Here, the subscript corresponds to the number of trace stages, and in Figure 2, the memory length is 8.
Since it is a stage, it can take values from 0 to 7. At the start of this trace, the ACS circuit corresponding to node: N ₀ is node: N ₁ N ₁ = 2 ^K-2 × PS ₀ + "N ₀ /2" where "N/2" is N/2. This means that the transition from the largest integer that does not exceed is selected as the surviving path, and the next step is to read the contents of the path memory (path selection signal) PS ₁ corresponding to the node N ₁ . This operation is repeated to trace the entire length of the path memory and obtain the decoded output from the node number of the node reached last. In that case, the last node number is expressed in binary notation and its MSB is decoded and output.

To explain this in more detail using the explanatory diagram of FIG. 2, in step 0, the node number N ₀ =7 with the minimum path metric value is selected, and the latest path selection signal PS, which is the content of the corresponding path memory, is selected. ₀
"1" is read out, and based on these, the calculation of the above-mentioned formula, ie, 4×1+3=7, is performed to obtain the node number N ₁ =7.

Therefore, in the next step 1, this node number
N ₁ = 7 and the corresponding path memory contents:
The node number N ₂ = 7 is determined based on “1” of PS ₁ , and in the subsequent step 2, the node number N ₂ =
7 and the contents of the path memory: PS ₂ =0, the node number N ₃ =3 is calculated. Thereafter, the node number N ₈ =4 is calculated in step 7 in the same manner. If this node number N ₈ is the last trace, the binary representation of node number 4 is “100”, so
The MSB “1” becomes the decoded output. Then, the node numbers in steps 0 to 7 are written into the trace memory 5 for each step.

In this way, for example, the node number N ₁ is given by the node number N ₀ and the contents of its path memory: PS ₀ . This means that when the node number is expressed as a binary number, node: N ₁ is derived by shifting node: N ₀ one lower digit and setting the path memory contents of node: N ₀ : PS ₀ as the highest. . That is, the node number 4 (ie, "100") of the last node reached in FIG. 2 is derived from the last three bits of the traced path selection signal. Therefore, the last path selection signal becomes the MSB of the node number, which becomes the decoded output.

According to the Viterbi decoding algorithm, the LSB (least significant bit) of the node number of the last reached node is originally used as the decoded output. However, the decoded output in this case is the path selection signal read out third from the end, and the remaining two tracings (K-2 times, where K is the constraint length) have no effect on the decoded output. Therefore, when the MSB is used as the decoded output as in the present invention, the number of memory accesses is fewer than when the LSB is used to obtain the same decoded output, so high-speed operation is possible. In other words, if the MSB is used for the decoded output,
If the entire path memory is traced by accessing the memory the same number of times as in the case of LSB, the path memory length will appear longer, that is, the effective length of the path memory will be longer than the actual path memory length, so the error rate due to path abort will increase. increase decreases.

〔Example〕

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

In the path tracing method described above, if the calculation of node numbers for path tracing is performed up to the last node reached in one decoding cycle, the number of accesses to the path memory increases, which reduces the decoding processing speed. In the embodiment described below, in order to solve this problem, there is a high probability that the maximum likelihood path in a certain decoding cycle and the maximum likelihood path in the previous decoding cycle will have almost the same shape, and Focusing on the fact that after the node numbers match, the subsequent paths will be the same,
Tracing is stopped when the calculated node number first matches the node number of the previous decoding cycle, and tracing is not performed until the end, reducing the number of accesses to the path memory, thereby improving the decoding processing speed.

Configuration of Example Device FIG. 3 is a block diagram of an example 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, 2
5 and 27 are data control units. The timing generation circuit 14 outputs a clock signal and a timing signal to be supplied to each section based on a high speed clock signal and a data clock signal. Further, the distributor 11 calculates a branch metric from the received code a, and sends this branch metric b to the ACS circuit 1.
This is in addition to 2.

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. 4, 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.

Explanation of Path Tracing The path tracing operation of the embodiment device will be explained below using FIG. 2 mentioned above.

As mentioned above, in FIG. 2, node number 7, which has the smallest path metric value of 62 among 82, 78, 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-1 × PS ₀₀ + N ₀₀ / "2" ...(1) is selected as the survival path, and next The path select signal PS ₀₁ of the contents of the path memory 16 corresponding to the node number N ₀₁ is read. Repeat these operations.
Note that "N ₀₀ /2" means the largest integer not exceeding N ₀₀ /2.

In FIG. 2, 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 ₀₀ of “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 MSB (most significant bit) of "1" becomes the decoded output. Then, the node numbers in steps 1 to 8 are written into the trace memory 17 for each step.

As described above, in a Viterbi decoder, there is generally 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, the maximum likelihood path from the previous decoding cycle is shifted by one step, and then
There is a high probability that it will be the same as the one with additional transitions.

FIG. 5 is an explanatory diagram of a path trace, showing a path trace in a decoding cycle following the decoding cycle of FIG. 2. The contents of the path memory are
By adding the latest path select signal to the beginning, the contents shown in FIG. 2 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. Second
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 MSB "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 comparator 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. .

According to experiments, the average number of traces is two or less unless the line error rate becomes extremely bad.

FIG. 6 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 in four parts of 16 bits each. 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 (the last node number MSB of the trace) is read from the trace memory, and then the trace start node number _N00 is written to 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. 3, 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 via the data control section 25 to the path memory 16 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 the 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. 6 shows a case where tracing ends in one decoding cycle, FIG. 7 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.

Path Trace Restart Method As described above, 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. In FIG. 8, a to c 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 ₂₀ , ..., 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) started, and the decoding cycle Suppose that tracing is performed from trace start node number N ₀₀ in decoding cycle 2 and completed in decoding cycle 2, then the next trace starts from trace start node number N ₁₀ selected in decoding cycle 1, and in this case, When the trace is completed 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.

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.

〔Effect of the invention〕

According to the present invention, it is possible to improve the decoding processing speed while using a RAM that is easy to integrate.

[Brief explanation of drawings]

Fig. 1 is a block diagram of the principle of the present invention, Fig. 2 is an explanatory diagram of path tracing, Fig. 3 is a block diagram of an embodiment of the invention, Fig. 4 is an explanatory diagram of address control, and Fig. 5 is an explanatory diagram of path tracing. , FIGS. 6 and 7 are operation time charts of path tracing, FIGS. 8 a to 8 c are diagrams explaining restart of path tracing, FIG. 11 and 12 show conventional path memories. 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 value for each node from a received code, and a plurality of ACS circuits 2 provided for each node.
Each individual calculates path metric values for two paths that can be selected based on the branch metric values from the distributor, compares the calculation results, and selects a surviving path from the two paths. , a device that outputs a path selection signal indicating the selection of the surviving path; a path memory 3 that stores the path selection signal in a predetermined number of stages corresponding to each node; a node number of an arbitrary node and a path of the path memory corresponding to the node number; a path trace control unit 4 that repeats over a predetermined number of stages the calculation of the node number of the node selected as a survivor in the previous stage based on the selection signal; and a trace that stores the node numbers traced by the path trace control unit over a predetermined number of stages. A Viterbi decoder comprising a memory 5 and configured to output the most significant binary digit of a node number at a predetermined stage of the trace memory as a decoded output.