JPH11186915A - Viterbi decoding device - Google Patents

Abstract

(57) [Summary] To reduce the circuit scale of a Viterbi decoding device. For example, a dual-port RAM 10 having 4 bits and 7 words and a dual-port RAM 11 having 8 bits and 7 words are provided. RAM
10 reads out the path selection information every clock and under the control of the control circuit 101 and reads out the read path selection information s1.
02 to the RAM 11 and the path selection information s1
01 (4 bits) is stored. On the other hand, under the control of the control circuit 101, the RAM 11 reads information of one word (8 bits), which is path selection information for two clocks and two times, and outputs read path selection information s103 and s104. Further, the RAM 11 stores the read path selection information s
102 and s103 are stored as one word. In the control circuit 101, based on the maximum likelihood state signal s105 and the read path selection information s102,
Performs decryption and initialization of the trace start state.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Viterbi decoding apparatus used for a maximum likelihood decoding method of a convolutional code used in, for example, satellite broadcasting.

[0002]

2. Description of the Related Art A Viterbi decoding method is known as one of methods for decoding a convolutional code. This Viterbi decoding method is a maximum likelihood decoding method for a convolutional code, and, from among code sequences that can be generated from a transmitting-side encoder, a sequence closest to a received code sequence (hereinafter, such a sequence is referred to as a maximum likelihood path). Error correction). That is, based on a transition diagram (hereinafter, referred to as a trellis) created based on an encoding method by a transmitting-side encoder, for example, a transition between a transition that can occur on the transition diagram and a received code sequence is performed. The path with the smallest Hamming distance is selected as the maximum likelihood path.

[0003] A Viterbi decoding device that performs the Viterbi decoding method includes:
A branch metric, that is, a branch metric calculation circuit that calculates a Hamming distance between a path reaching each state on the trellis and a received code sequence according to a clock, and calculates a state metric based on the branch metric, and calculates a state metric value. An ACS circuit for comparing and selecting the maximum likelihood path, a normalizing circuit for normalizing the value of the state metric, a state metric storage circuit for storing the value of the state metric, and a path memory circuit for generating decoded data according to the result of the selection by the ACS. It is configured to be provided.

[0006] Here, a path memory circuit performs a register transition method of transitioning path selection contents using a register row, and a path selection circuit is stored using a RAM, and the stored contents are traced and decoded. There are two types of methods that perform the method. Hereinafter, these two types of methods will be described.

In a register transition method generally used in a conventional Viterbi decoding device, a memory cell including a selector and a register is arranged on a trellis in a path memory circuit, and path selection information output from an ACS circuit is output. The content of the register is transited based on. FIG. 23 illustrates an example of a memory cell configuration. FIG. 24 shows an example of the arrangement of the memory cells when the constraint length = 3 (in FIG. 24, the memory cells are denoted by MS). With such a configuration, information corresponding to the surviving path from each state is stored in the register of each memory cell. The number of stages corresponding to the truncation length is arranged in the memory cell, and the information for the maximum likelihood path is selected by selecting the output of the maximum likelihood state from the outputs of the final stage, and the decoded data is output. In the memory cell, the number of stages corresponding to the truncation length is arranged, and the information corresponding to the maximum likelihood path is selected by selecting the output of the maximum likelihood state from the outputs of the final stage, and the decoded data is output.

[0006] Such a register transition method has an advantage that high-speed operation is possible, but has a disadvantage that the circuit scale becomes enormous when the truncation length is long. In particular, recently, applications in which the truncation length exceeds 100 have emerged, and the enlargement of the circuit scale has become a serious problem.

In view of these problems, in recent years, RA
The path information is stored using M (Random Access Memory),
A method of decoding stored information by tracing the information has been actively studied. Hereinafter, this method is called a traceback method.

[0008]

According to the path memory circuit performing the trace-back method, a path memory circuit having a much smaller circuit scale than the register transition method can be constructed. However, since the total number of words in the RAM reaches twice or more the truncation length, a large circuit size is still required.

The present invention has been proposed in view of such circumstances, and it is therefore an object of the present invention to provide a Viterbi decoding device with a reduced circuit scale.

[0010]

According to a first aspect of the present invention, there is provided a path memory for storing path selection information in each transition state of a convolutional code using a rewritable memory, and the path memory stores the path selection information. In a Viterbi decoding device that performs Viterbi decoding by tracing information for a truncated length, a rewritable memory that stores an integer multiple of the number of states is used, and one address of the rewritable memory is used for a plurality of times. A Viterbi decoding device storing path selection information.

According to the invention described above, it is possible to store path selection information for a plurality of times at one address on a rewritable memory. Therefore, the number of RAMs can be reduced.

[0012]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A first embodiment of the present invention will be described below with reference to the drawings. First, the overall configuration of the first embodiment of the present invention will be described with reference to FIG. In the first embodiment of the present invention, a branch metric calculation circuit 701, an ACS circuit 702, a normalization circuit 70
3, a configuration including a state metric storage circuit 704 and a path memory circuit 705. When data received from a transmission side via a transmission line is input, a code sequence that can be generated from an encoder on the transmission side. A maximum likelihood path is selected from among them, and decoded data is generated based on the selected content.

That is, assuming, for example, a transition diagram (hereinafter, referred to as a trellis) as shown in FIG. 2, which is created based on an encoding method by an encoder on the transmission side, among transitions that can occur on the transition diagram, Therefore, for example, a path having the minimum Hamming distance from the received code sequence is selected as the maximum likelihood path.

When the received data signal s701 is input, the branch metric calculation circuit 701 calculates a branch metric of the received data and outputs the calculation result as a branch metric signal s702. The ACS circuit 702 determines a branch metric and a state metric for each of two paths joining a certain state based on the branch metric signal s 702 and the state metric signal s 705 supplied from the state metric storage circuit 704. Add and compare the added values, select the one with the highest likelihood based on the comparison result,
Let it be a new state metric.

The contents of such selection are stored in path selection information s7.
06, the state number having the smallest state metric is output as the maximum likelihood state signal s707, and the newly obtained state metric is output as a new state metric signal s703.

Here, a method of selecting a path will be described by taking a case where the constraint length = 3 as an example. The trellis in FIG.
States 00, 01, 10, 11 and the constraint length =
3 is an example of a trellis in the case of No. 3; Here, arrows indicate paths that can occur in each time slot, a path corresponding to decoded data '0' is indicated by a dotted line, and a path corresponding to decoded data '1' is indicated by a solid line. There are two paths merging in every state for each time slot. Therefore, for each of the two paths joining a certain state, a comparison is made by adding the Hamming distance (branch metric) between the received signal and the path and the cumulative sum of the branch metrics up to that point (state metric). The one with the highest likelihood is selected based on the comparison result.

The normalization circuit 703 normalizes using a method of subtracting the minimum state metric from the new state metric signal s703 output from the ACS circuit 702, and converts the new state metric signal s703 to a value within a preset range. And outputs the same as the normalized state metric signal s704. The state metric storage circuit 704 stores the number of normalized state metric signals s704 output from the number of normalization circuits 703 equal to the number of states, and returns this to the ACS circuit 702 as a state metric signal s705.

Prior to describing the path memory circuit 705, in order to facilitate understanding, a trace operation in a general traceback method which has been conventionally used will be described by taking a case where a constraint length = 3 as an example. I do. In FIG.
Consider the case of tracing from state 01. The state that may transition to state 01 is state 00
And state 10. Here, the path memory is set to 0 when the path on the state 00 side is selected,
When the side path is selected, 1 (that is, the most significant bit of the previous state) is stored.

The input is 1 when transitioning from any state, which is represented by the least significant bit of state 01. As described above, the trace operation may be performed as follows. As shown in FIG. 4, the least significant bit of the trace start state that starts tracing is a decoding bit, and the number of the next trace state to be traced following the trace start state is the second lower bit from the most significant bit of the trace start state. By the time, a bit in the path memory is newly added as the most significant bit. By such an operation, the selected path can be traced back from the state having the minimum state metric.

In order to operate the Viterbi decoder at high speed, the RAM can be accessed only once every clock.
A paper by Rim et al. ("MEMORY MANAGEMENT I
N HIGH-SPEED VITERBI DECODERS ", IEEE VLSI signal pr
Ocessing, 8 Oct. 1995). FIG. 5 shows an example of such a path memory circuit. Such a path memory circuit has a 1-write-1 read dual-port R with a bit number = 4 and a word number = 4.
It has one AM and two 1-write-1 read dual-port RAMs with 4 bits and 7 words. This path memory circuit, for a code of constraint length = 3,
Decoding with a truncation length = 6 can be performed.

In the path memory circuit shown in FIG.
20 reads the path selection information every clock according to the control signal s1206 generated by the control circuit 1201, and outputs the read path selection information s1202. Further, the RAM 120 stores a path selection signal s1201 input from the ACS circuit 702. On the other hand, the RAM 121 reads the path selection information every clock according to the control signal s1206 generated by the control circuit 1201, and outputs the read path selection information s1203. The RAM 121 stores RA
The path selection signal s1202 input from M120 is stored. Further, the RAM 122 stores the control circuit 12
In accordance with the control signal s1206 generated in step 01, the path selection information is read every clock and the read path selection information s1204 is output. The RAM 12
2 is a path selection signal s12 input from the RAM 121
03 is stored.

FIG. 6 shows the timing of the memory operation based on the control circuit 1201. The read path selection information s1202, s1203, s1204 is input to the control circuit 1201. The control circuit 1201 initializes the trace start state on the basis of the maximum likelihood state signal s1205 at every (discontinuation length / 2) clocks (in this example, 6/2 = 3 clocks) while reading the read path selection information. s1202, s120
3. Trace in s1204 is performed to determine the trace state at the next clock. Control circuit 1201
Simultaneously obtains a decoded bit based on the trace state for the read path selection information s1204 and outputs it as a decoded bit signal s1207.

The decoded bit signal s1207 is input to an output buffer 1202. The output buffer 1202 rearranges the decoded bit signal s1207 in the original time series and outputs the result as a decoded output signal s1208. The path memory circuit having the above configuration is generally used for performing Viterbi decoding by the traceback method.

Here, the memory operation of FIG. 6 will be described more specifically with reference to FIGS. 7, 8 and 9. 7 to 9 illustrate writing / reading to / from three dual-port RAMs at successive times. FIG. 7 illustrates time 1 to time 6 and FIG. 8 illustrates time 7 to time 13 for convenience of the description space. Further, FIG.
0 is shown. As described above, one of them (that is, the RAM 120) has the number of bits = 4 and the number of words = 4, and two of them (the RAM 121 and the RAM 121).
122) has the number of bits = 4 and the number of words = 7. Here, the addresses of the respective memories are 0, 1, 2,... In order from the left.

At times 1, 2, and 3, the RAM 120
, The path selection information 1, 2, and 3 are sequentially written at addresses 0, 1, and 2, and at time 4, the subsequent path selection information 4 is written at address 3 of the RAM 120, and
From address 2 of AM 120 to address 4 of RAM 121
Path selection information 3 is copied. At the next time 5, the subsequent path selection information 5
Is written, and the path selection information 2 is copied from the address 1 of the RAM 120 to the address 3 of the RAM 121. Hereinafter, until time 9, the RAM 120
The path selection information is written into 121. At time 9, all addresses of the RAM 120 and the RAM 121
The path selection information is written in all the addresses other than the address 5 in FIG.

At time 10, the RAM 12
Subsequent path selection information 10 is written at address 3 of 0, path selection information 9 is read from address 2 of RAM 120 and traced, and this path selection information 9 is copied to address 5 of RAM 121. Here, 't' attached to the read arrow indicates that tracing is performed, and 'd' indicates that tracing is performed for decoding. At the same time, RAM 5
The path selection information 3 is copied from the address 4 of 121. Hereinafter, at times 11, 12, and 13, writing, tracing, and copying are similarly performed.

Further, at time 14, the RAM 120
The subsequent path selection information 14 is written in the address 1 of the RAM 120, and the path selection information 1
2 is read and traced, and the path selection information 12 is copied to the address 2 of the RAM 121. At the same time, the path selection information 6 is read from the address 1 of the RAM 121 and traced, and the path selection information 6 is copied to the address 2 of the RAM 122. At time 15, writing, tracing and copying are performed in the same manner.

FIG. 6 shows the operation after time 16. In the first clock of FIG. 6 corresponding to the time 16, the path selection information 15 is read out from the address 2 of the RAM 120 and traced, and the path selection information 15 is copied to the address 6 of the RAM 121. At the same time, the path selection information 9 is read from the address 5 of the RAM 121 and traced, and the path selection information 9 is copied to the address 6 of the RAM 122. Furthermore, the path selection information 3 is read from the address 5 of the RAM 121, traced, and decoded. Then, at this clock, the trace start state is initialized.

Writing, tracing, copying, and decoding are also performed at the second and subsequent clocks in FIG. 6 corresponding to time 11. Then, the trace start state is initialized once every three clocks. The Viterbi decoding by the traceback method can be performed by the memory operation as described above.

On the other hand, the present applicant has proposed the following method using a configuration as shown in FIG. 10 as another method for realizing Viterbi decoding by the traceback method. In other words, three 1-write-1 read dual-port RAMs with the number of bits = 4 and the number of words = 4 are provided, and tracing for three times is performed during one clock. This path memory circuit decodes a code with a constraint length of 3 and a cutoff length of 6.

The path selection signal s input from the ACS circuit
1402, every clock, RAM142 → RAM141 → RAM140 → RA according to a write control signal s1403 generated by the control circuit 1401.
Are stored in the RAM in the order of M142 → RAM141. From the RAM 140, the RAM 141, and the RAM 142, every clock and all R
The path selection information is read from the AM, and the read path selection information s1405, s1406, and s1407 is input to the trace circuit 1402.

FIG. 11 shows the timing of the memory operation based on the control circuit 1401.

Further, in FIG.
At 402, the RAM 140, the RAM 141, and the RAM 14
2 read path selection information s1405, s14
06, s1407 and the trace start state information s1408 generated by the control circuit 1401 are traced for three times, and the result is input to the control circuit s1401 as a trace result signal s1409. The control circuit s1401 obtains the trace start state of the next clock based on the trace result signal s1409 and the maximum likelihood state signal s1401 while initializing the trace start state for every censoring length / 2 clocks.

On the other hand, trace start state information s140
8 is also input to the output buffer 1403. The output buffer 1403 buffers the lower three bits of the trace start state information s1408 after tracing for the censoring length or more as decoded bits, rearranges them in the original time series, and then decodes the decoded bit signal. Output as s1410. The Viterbi decoding by the traceback method is also possible with the path memory circuit having the above configuration.

In the above-described traceback method, a path memory circuit having a much smaller circuit scale than the register transition method can be configured. However, since the total number of words in the RAM reaches twice or more the truncation length, a large circuit size is still required. One embodiment of the present invention realizes further reduction in the circuit scale of a path memory circuit.

Referring to FIG. 12, a description will be given of a path memory circuit 705 according to an embodiment of the present invention. When decoding the code with the constraint length = 3 and the code with the censoring length = 6, the path memory circuit 705 uses the number of bits = 4 (the same as the number of states) and the number of words = 7 (divides the censoring length 6 by 2). One 1-write-1 read dual-port RAM (ie, RAM 10) and the number of bits =
8 (double the number of states) and the number of words = 7 (discontinuation length 6
Is obtained by dividing one by two and adding one (one), and a single write-one-read dual-port RAM (that is, RAM 11), which is similar to the memory operation described above with reference to FIG. It is possible to perform a memory operation.

In FIG. 12, the RAM 10 stores a control signal s106 generated by the control circuit 101.
, The path selection information is read every clock and the read path selection information s102 is output. Furthermore, RA
M10 stores the path selection information s101 input from the ACS circuit 702. The RAM 11 reads one word of information, which is path selection information for two clocks and two clocks, according to the control signal s106 generated by the control circuit 101, and reads out the read path selection information s1.
03, and outputs s104. Further, the RAM 11 stores the read path selection information s102 and s103 as one word.

The read and write operations of the RAM 10 and RAM 11 will be described with reference to FIG. FIG.
As shown in FIG. 3A, the path selection signal a (4
Bit) and the path selection signal b (4 bits) is read from the RAM 11. Then, the path selection signals a and b are set as one word (8 bits) again in the RAM 11.
(FIG. 13B). On the other hand, the read path selection information s102, s103, s104 is input to the control circuit 101.

The control circuit 101 initializes the trace start state on the basis of the maximum likelihood state signal s105 at every censoring length / 2 clocks (here, 6/2 = 3 clocks), and reads out the read path selection information s102,
The tracing of s103 and s104 is performed to determine the trace state at the next clock. At the same time, the control circuit 101 obtains a decoded bit based on the trace state for the read path selection information s104 and outputs it as a decoded bit signal s107.

By performing such an operation with the memory operation at the timing shown in FIG. 14, the same operation as the memory operation described above with reference to FIG. 11 can be performed. The decoded bit signal s107 is input to the output buffer 102, and the output buffer 102 rearranges the decoded bit signal s107 in the original time-series order and outputs it as a decoded output signal s110.

Referring to the memory operation shown in FIGS. 13 and 14, FIG. 15, FIG. 17, FIG.
8 will be described more specifically. 15 to 18 illustrate writing / reading to / from the RAM 10 and the RAM 11 at successive times.
FIG. 15 illustrates time 1 to time 4 and FIG. 16 illustrates time 5 to time 9 for convenience of the description space.
FIG. 17 illustrates time 10 to time 14, and FIG. 18 illustrates time 15 to time 19. As described above, the RAM 10 has the number of bits = 4 and the number of words = 7, and the RAM 11 has the number of bits = 8 and the number of words = 7.
7 is provided. Here, the addresses of the respective memories are 0, 1, 2,... In order from the left.

At times 1, 2, and 3, path selection information 1, 2, and 3 are sequentially written to addresses 0, 1, and 2 of the RAM 10, and at time 4, the address 3 of the RAM 10 is written.
The subsequent path selection information 4 is written into the RAM and the RAM
The path selection information 3 is copied from the address 2 of 10 to the address 4 of the RAM 11. Since the number of bits of the RAM 11 is 8 bits, when the path selection information 3 (4 bits) is written, it means that writing has been performed in half the area. At the next time 5, the following path selection information 5 is written to the address 2 of the RAM 10, and the path selection information 2 is written from the address 1 of the RAM 10 to the address 3 of the RAM 11.
Is copied. Hereinafter, the path selection information is sequentially written to the RAM 10 and the RAM 11 until time 9. At time 9, all addresses of the RAM 10 and the RAM
The path selection information is written in all the addresses other than the address 5 of the address 11. However, each address of the RAM 11 is recorded only in a half area.

At time 10, the succeeding path selection information 10 is written into the address 3 of the RAM 10, and
The path selection information 9 is read from the address 2 of the RAM 10 and traced. On the other hand, the path selection information 3 is read from the RAM 11. Then, the path selection information 9 and the path selection information 3 are rewritten as one word (8 bits) by R
It is written to address 5 of AM11. 15 to 18
In the above, 't' attached to the read arrow indicates tracing, and 'td' indicates tracing and decoding. Hereinafter, at times 11 and 12, writing, reading, tracing, and writing in units of 8 bits are similarly performed.

At time 13, subsequent path selection information 14 is written to address 1 of RAM 10, and
The path selection information 12 is read from the address 1 of the RAM 10 and traced. On the other hand, address 1 of RAM 11
Is read and traced. Then, the path selection information 12 and the path selection information 6 become 1 again.
The data is written to the address 2 of the RAM 11 as a word (8 bits). Hereinafter, at times 14 and 15, writing, reading, tracing, and writing in units of 8 bits are similarly performed.

FIG. 14 shows the operation after time 16. In the first clock of FIG. 14 corresponding to the time 16, the subsequent path selection information 16 is written to the address 3 of the RAM 10, and the path selection information 15 is read from the address 2 of the RAM 10 and traced. On the other hand, the path selection information 9 and 3 are read from the address 5 of the RAM 11 and traced, and decoding based on the path selection information 3 is performed. Then, the path selection information 15 and the path selection information 9 are replaced by one word (8 bits).
At the address 6 of the RAM 11. Also,
At this clock, the trace start state is initialized.

In the second clock of FIG. 14 corresponding to the time 17, the subsequent path selection information 17 is written to the address 2 of the RAM 10, and the path selection information 14 is read from the address 1 of the RAM 10 and traced. On the other hand, the path selection information 8 and 2 are read from the address 8 of the RAM 11 and traced, and decoding based on the path selection information 2 is performed. Then, the path selection information 14 and the path selection information 8 are stored as one word (8 bits) in the RAM again.
11 is written to address 5.

In each of the subsequent clocks, writing, reading, tracing, and writing in units of 8 bits are similarly performed. Writing, tracing, copying and decoding are performed. Then, the trace start state is initialized once every three clocks.

According to the configuration of the path memory 705 as described above, the total storage capacity of the RAM is the same as that of the related art,
The number of M is three (RAM 120, RAM 12 in FIG. 5).
1, RAM 122) and two (RAM 10,
RAM 11). In general, for the same storage capacity, the smaller the number of RAMs, the smaller the area occupied by the RAMs. Therefore, in the path memory having the configuration as shown in FIG.
The area occupied by M can be reduced. For this reason, the circuit scale of the path memory can be reduced, which can contribute to a reduction in the circuit scale of the entire Viterbi decoding device.

Next, another embodiment of the present invention using a path memory circuit having a different configuration from the path memory circuit in one embodiment of the present invention will be described. FIG.
FIG. 9 illustrates a configuration of a path memory circuit according to another embodiment of the present invention. Such a path memory circuit has a constraint length =
When decoding the code of 3 with the truncation length = 6,
Number of bits = 12 (3 times the number of states 4) and number of words = 4
A configuration in which one write-one-read dual-port RAM of (2/3 times the censoring length 6) is provided to trace three times during one clock.

The path selection signal s input from the ACS circuit
402 is stored in registers 402 and 403,
According to the control signal s405 generated by the control circuit 401, path selection information for three clocks is stored in the RAM 40 once every three clocks. In accordance with the control signal s405, the path selection information for each clock and three clocks is read from the RAM 40, and the read path selection information s407 is input to the trace circuit 405.

FIG. 20 shows the timing of the memory operation based on the control circuit 401. The trace circuit 405 traces three times according to the read path selection information s407 output from the RAM 40, the trace start state information s407 generated by the control circuit 401, and the trace start state information s406 generated by the control circuit 401. The result is input to the control circuit 401 as a trace result signal s408.

The control circuit 401 initializes the trace start state based on the trace result signal s408 and the maximum likelihood state signal s401 for each censor length / 2 clocks (here, 6/2 = 3 clocks). Then, the trace start state of the next clock is obtained. On the other hand, the trace start state information s406 is also input to the output buffer 406. The output buffer 406 buffers the lower three bits of the trace start state information s406 after tracing the length of the censoring length or more as decoded bits, rearranges them in the original chronological order, and outputs them as decoded bit signals s409.

The memory operation shown in FIG. 20 will be described more specifically with reference to FIGS. 21 and 22. FIGS. 21 and 22 show RAMs at successive times.
FIG. 4 illustrates writing / reading to / from the memory 40. Due to the space of the description space, FIG.
FIG. 22 shows time until time 6, and FIG. 22 shows time 7 to time 12. As described above, the RAM 40 stores the number of bits =
The dual port RAM has 12 words and 4 words. Here, the addresses in the RAM 40 are all 0, 1, 2,...

At times 1 and 2, the register 402,
The path selection information 1 and 2 are sequentially stored in 403, and the path selection information 1, 2 and 3 (4 × 3 = 12 bits in total) are written to the address 1 of the RAM 40 at time 3. Thereafter, at times 4 and 5, the path selection information 4 and 5 are sequentially stored in the registers 402 and 403, and at time 6 the path selection information 4, 5 and 6 are written to the address 2 of the RAM 40. Similarly, at time 9, path selection information 7, 8, 9 is written to address 3 of RAM 40.

FIG. 20 shows the operation after time 10. At the first clock in FIG. 20 corresponding to time 10, path selection information 7, 8, 9 is read from address 3 of RAM 40. As described above, the trace circuit 405 traces based on the path selection information for these three times. Similarly, at the second clock in FIG. 20 corresponding to the time 11, the path selection information 4, 5 and 6 is read from the address 2 of the RAM 40 and traced. Here, in FIGS. 21 and 22, "t" attached to the read arrow indicates that tracing is performed, and "d" indicates that tracing is performed for decoding. Further, at the third clock of FIG. 20 corresponding to time 12, path selection information 1, 2, and 3 are read from address 1 of RAM 40, and traced and decoded. At time 12, address 0 of RAM 40
The subsequent path selection information 10, 11, and 12 are written in.

FIG. 20 corresponding to the subsequent time 13
The path selection information 10, 11, and 12 are read from the address 0 of the RAM 40 and traced at the fourth leading clock. At time 13, the trace start state is initialized. Thereafter, the tracing / writing and the initialization of the decoding / tracing start state are sequentially performed using three clocks as a unit of operation.

In the path memory circuit having the above configuration, the total storage capacity of the RAM is the same as the conventional one,
The number of RAMs can be reduced. That is, the number of RAMs can be reduced to one while three RAMs are conventionally provided in the path memory circuit. Therefore, the area occupied by the RAM in the path memory can be reduced, the circuit size of the path memory can be reduced, and the circuit size of the entire Viterbi decoding device can be reduced.

In the above embodiment of the present invention and another embodiment of the present invention, the case where the constraint length = 3 and the cutoff length = 6 has been described. However, the constraint length and the cutoff length are not limited to these values. It can be any value.

[0059]

As described above, according to the present invention, since the number of RAMs in the path memory circuit is reduced, the area of the RAM occupying the circuit can be reduced. Therefore, it is possible to provide a Viterbi decoding device having a small circuit scale.

[Brief description of the drawings]

FIG. 1 is a block diagram for explaining an overall configuration of an embodiment of the present invention.

FIG. 2 is a block diagram for explaining a transition diagram when a constraint length = 3.

FIG. 3 is a schematic diagram for explaining the principle of tracing in the traceback method.

FIG. 4 is a schematic diagram for explaining a tracing method in a trace-back method.

FIG. 5 is a block diagram for explaining an example of a path memory circuit that performs a general traceback method that has been conventionally used.

FIG. 6 is a schematic diagram for explaining a memory operation in the path memory circuit shown in FIG. 5;

FIG. 7 is a schematic diagram for more specifically describing a memory operation in the path memory circuit shown in FIG. 5;

FIG. 8 is a schematic diagram for more specifically describing a memory operation in the path memory circuit shown in FIG. 5;

FIG. 9 is a schematic diagram for more specifically describing a memory operation in the path memory circuit shown in FIG. 5;

FIG. 10 is a block diagram illustrating an example of a path memory circuit that performs the previously proposed trace-back method.

FIG. 11 is a schematic diagram illustrating a memory operation in the path memory circuit shown in FIG. 10;

FIG. 12 is a block diagram for describing a path memory circuit according to an embodiment of the present invention.

FIG. 13 is a schematic diagram for explaining a read and write operation of the memory according to the embodiment of the present invention;

FIG. 14 is a schematic diagram illustrating a memory operation according to an embodiment of the present invention.

FIG. 15 is a schematic diagram for more specifically explaining a memory operation in the path memory circuit of FIG. 12;

FIG. 16 is a schematic diagram for more specifically explaining a memory operation in the path memory circuit of FIG. 12;

FIG. 17 is a schematic diagram for more specifically explaining a memory operation in the path memory circuit of FIG. 12;

FIG. 18 is a schematic diagram for more specifically explaining a memory operation in the path memory circuit of FIG. 12;

FIG. 19 is a block diagram for describing a path memory circuit according to another embodiment of the present invention.

FIG. 20 is a block diagram for describing a memory operation according to another embodiment of the present invention.

FIG. 21 is a schematic diagram for more specifically describing a memory operation according to another embodiment of the present invention.

FIG. 22 is a schematic diagram for more specifically describing a memory operation in another embodiment of the present invention.

FIG. 23 is a schematic diagram for describing memory cells of a path memory in the register transition method.

FIG. 24 is a schematic diagram for explaining an arrangement of memory cells in a path memory in a register transition method.

[Explanation of symbols]

705: Path memory circuit, 101: Control circuit, 402, 403: Register

Claims (3)

[Claims] 1. A path memory for storing path selection information in each transition state of a convolutional code using a rewritable memory, and tracing information stored in the path memory by a truncation length to trace Viterbi decoding. A rewritable memory that stores an integer multiple of the number of states using a rewritable memory, and stores path selection information for a plurality of times at one address of the rewritable memory. Viterbi decoding device. 2. The method according to claim 1, wherein the number of bits = the number of states, and the number of words = the truncation length /
One 1-write-1 read dual-port RAM, 2 + 1, 1-write-1 read dual-port RAM, and the number of bits = the number of states × 2, and the number of words = cutoff length + 1, are 1 A Viterbi decoding device comprising: 3. The Viterbi decoding device according to claim 1, further comprising one 1-write-1 read dual-port RAM in which the number of bits = the number of states × 2 and the number of words = the censoring length + 1. apparatus.