KR20040092783A - Trellis decoder using viterbi algorithm and grouping method of the same - Google Patents

Abstract

PURPOSE: A trellis decoder using a Viterbi algorithm and a method for grouping a state thereof are provided to reduce a total chip size and improve a degree of integration by reducing an area between a path metric memory and an adder/comparator/selector. CONSTITUTION: A memory bank is divided into plural memory banks. The divided memory banks are used for grouping path metrics provided from an adder/comparator/selector. A switch is arrayed between the adder/comparator/selector and the bank memory in order to connect the adder/comparator/selector to the bank memory.

Description

TRELLIS DECODER USING VITERBI ALGORITHM AND GROUPING METHOD OF THE SAME}

The present invention relates to a Viterbi decoder, and more particularly, to a method of managing a path metric memory for reducing the connection area of a Viterbi decoder.

Channel coding, which is the primary purpose of a communication system, for accurate information transfer is a major research subject in a digital communication system. Digital communication systems transmit data through source coding for discretizing analog signals and channel coding to correct errors on the channel, respectively, in order to overcome channel capacity limitations and ensure information reliability. do.

Channel coding is largely divided into a block code and a convolutional code, and the block code is divided into a linear code and a cyclic code.

The fundamental difference between block code and convolutional code is the presence of storage. The coder of the block code is an inorganic memory that generates k-bit information into an n-bit codeword, whereas the coder of the convolution code is determined not only by the current input of the output series but also by the past input sequence. It is considered a device with memory.

Convolutional coding, which has better error correction efficiency than block coding, is mainly used. Convolutional coding requires a large amount of memory during decoding and a decoding delay occurs, which requires a decoding algorithm capable of real-time processing.

The Viterbi algorithm, which is the maximum likelihood decoding algorithm of convolutional coding, has been proposed.

The Viterbi algorithm is an algorithm that performs maximum likelihood decoding and reduces the amount of computation required by using the Trellis diagram. This algorithm allows only one Survivor path to exist in a state by comparing the similarity between the paths input to each state and the received signal. This process is repeated at each stage of the trellis diagram over time. Therefore, the amount of computation required by the Viterbi algorithm does not depend on the length of the transmitted code string, but depends on the state number.

1 is a block diagram of a trellis decoder to which the Viterbi algorithm is applied. The trellis decoder includes a branch metric calculation unit 11 (hereinafter referred to as BMC) and an add comparison selection unit 12. A selection unit (hereinafter referred to as ACS), a path metric network (hereinafter referred to as PMN) and a survivor memory unit 14 (hereinafter referred to as SMU).

Here, a metric is a value obtained by calculating a distance between codes in a branch corresponding to a received signal, and this distance serves as a reference for signal discrimination. The metric is a Hamming distance in case of hard-decision decoding, and an Euclidean distance in case of soft-decision.

The above-described branch metric calculation unit 11 receives the received symbol and calculates the distance between the path passing through each state and the received symbol by using the trellis degree, and adds the resultant branch metric BMt to the comparison comparison selection unit. Provided by (12).

The addition comparison selecting unit 12 serves to select a path having a minimum path metric among the paths input to each state at each time t, and a plurality of branch metrics BMt provided from the branch metric calculation unit 11. And adds the previous path metric (PMt-1) provided from the path metric network 13 (scaling a number of branch metrics merged in the current state to the previous path metric) and accumulated path metrics at the current stage. Are compared to select the path metric with the smallest value among them.

The route metric thus selected is called a surviving route metric and is provided to the route metric network 13. Then, the survivor memory 14 is provided to the survivor memory unit 14 to trace back the survival path according to the traceback algorithm.

The route metric network 13 receives the survivor metric output from the add comparison selector 12 and stores the survivor metric, and then provides the survivor metric to the add comparison selector 12 to be used as a previous route metric for each state in the next step. It plays a role.

The survivor memory 14 outputs the last reconstructed symbol according to the traceback algorithm while maintaining the survival path information by the decoding depth in order to trace back the survival path of each state and perform the reconstruction symbol. .

In the conventional trellis decoder having such a structure, the branch metric calculation unit 11 or the addition comparison selection unit 12 increases the amount of hardware or the amount of calculation according to the number of states of the trellis code.

This is because conventionally, each state has one branch metric calculation unit and one addition comparison selection unit, and separately calculates only the metrics necessary for each state.

For example, if you examine the trellis in the branch metric of a 16-state TCM decoder, you will have four branch metrics for each state, so you need to calculate a total of 64 (16 × 4) branch metrics. Add operation using, and must perform 64 absolute calculations.

Here, the branch metric between the previous state and the current state is a value calculated from the difference between the input signal output from the NTSC interference cancellation filter and the reference value. If the branch of the correct path is a branch metric is exactly 0, In the communication environment, the branch metric has a value close to zero due to the influence of noise. That is, the data input to the decoder enters with the noise mixed in the code symbol, calculates the difference from the reference value of the code symbol, sets it as a branch metric, and compares this metric to decode the signal closest to the original signal. .

However, since the reference value is always determined for each branch of each state, the branch metrics of each state can be examined to show that there are branches having the same value (metric).

As described above, the conventional TCM decoder has a problem of inefficiency of repeatedly calculating the same branch metric BM by separately implementing the branch metric calculation unit and the addition comparison selection unit for each state. In addition, there is a problem in that the cost and the area are increased due to the considerable amount of hardware for calculating each branch metric.

In order to reduce the size of the decoder, there is a method of serial processing with one addition comparison selection unit and a method of arranging the addition comparison selection unit in parallel for high performance.

In the first case, the size of the decoder can be reduced, but the performance is inferior. In the second case, the performance is improved but the area is increased.

Therefore, a compromise between the two methods described above is a method in which several states share the addition comparison selection unit. In order to use this method, the existing scheme (Scheme) uses a multiplexer to connect between the add comparison selector and the path metric network.

2 is a block diagram illustrating a routing network according to the prior art.

Referring to FIG. 2, four addition select comparison units ACS0 to ACS3, four demultiplexers DMUX, four branch metric calculation units B0 to B3, and four multiplexers MUX are arranged.

On the other hand, when the routing network shown in FIG. 2 is applied, a problem arises in that the connection area between the addition comparison selection unit and the path metric network becomes large.

The present invention has been proposed to solve the above problems of the prior art, and provides a trellis decoder state grouping method using a Viterbi algorithm capable of reducing the connection area of the Viterbi decoder using the Viterbi algorithm. There is a purpose.

1 is a block diagram of a trellis decoder to which the Viterbi algorithm is applied.

2 is a block diagram illustrating a routing network according to the prior art.

3 is a diagram illustrating swapped state grouping of a 16 state Viterbi decoder according to one embodiment of the present invention;

4 is a block diagram illustrating a routing network according to an embodiment of the present invention.

5 illustrates an in-place updating technique according to an embodiment of the present invention.

Explanation of symbols on the main parts of the drawings

ACS0 to ACS3: Addition comparison selection section

B0-B3: Branch metrics

In order to achieve the above object, in the state grouping of the trellis decoder using the Viterbi algorithm, the present invention divides the memory banks and replaces the path metrics provided from the addition comparison selection unit with each other in the divided memory banks. A state grouping method of a trellis decoder using a Viterbi algorithm is provided.

In addition, in order to achieve the above object, the present invention provides a trellis decoder using the grouping method, wherein a switch is arranged between the addition comparison selection unit and the bank memory to provide a connection between the path metric memory and the addition comparison selection unit. Provided is a trellis decoder using a Viterbi algorithm, characterized in that the connection.

As mentioned in the problem of the prior art, the method of sharing several addition comparison selections with several states in order to reduce the area without significantly degrading the performance leads to the total connection area between the addition comparison selection and the path metric memory. It takes up a significant portion of the chip size. Therefore, reducing this portion is an important problem.

When the Viterbi decoder having 16 states is configured in parallel in design, 16 addition comparison selection parts are required. Therefore, the present invention has only four addition comparison selection sections, and four states are processed while sharing one addition comparison selection section. At this time, the interconnection between the addition comparison selection unit and the memory storing the calculated path metric value becomes complicated.

Conventionally, there is a method of using a 4 * 1 multiplexer, but in this case, there is a disadvantage in that the interconnection area becomes large. Therefore, in the present invention, when the path metric value is inserted into the metric memory, the connection area can be reduced by using a stata-grouping technique and an in-place updating technique.

DETAILED DESCRIPTION Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art may easily implement the technical idea of the present invention. do.

3 is a block diagram illustrating swapped state grouping of a 16 state Viterbi decoder according to an embodiment of the present invention.

3 shows an example composed of a memory bank of B0 to B3, 16 states of S0 to S15, and four ACSs.

According to the state grouping proposed in the present invention, the connection from the bank to the ACS is fixed, and more than half high states are exchanged to store four output path metrics calculated from the four ACSs in different banks. Swapped. In addition, you must determine which states are calculated in the ACS.

State assignments have a big impact on routing networks. The new path metrics S0 and S8 are calculated from S0 and S1, and the new path metrics S2 and S10 are calculated from S4 and S5.

If ACS0 and ACS1 are specified as (S0, S2) and (S8, S10) respectively, ACS0 and ACS1 must be connected to B0 and B2. To simplify this connection, ACS0 and ACS1 can be specified to calculate (S0, S10) and (S8, S2), respectively.

In this case it is possible to connect ACS0 to B1 and ACS1 to B2. If Sn = 1 in the encoding of the input states, this technique is called swapped computing, that is, because the high numbered state is calculated at the lower ACS.

By applying the above state grouping and swapped computing, the output path metrics calculated at ACS0 are stored at B0 or B1. Similarly, ACSs are also connected to only two banks, as shown in Table 1 summarized below.

ACS0 (S0, B0) (S10, B0) (S5, B1) (S15, B1) ACS1 (S8, B2) (S2, B2) (S13, B3) (S7, B3) ACS2 (S1, B1) (S11, B1) (S4, B0) (S14, B0) ACS3 (S9, B3) (S3, B3) (S12, B2) (S6, B2)

The leftmost column here represents the ACS, while the rightmost column represents each state and bank.

4 is a diagram illustrating a routing network according to an embodiment of the present invention.

Referring to FIG. 4, two switches are arranged to control each connection, and each of 2 * 2 switches connects two ACSs and a bank memory. All switches are simultaneously controlled by S _v-1 of the input state encoding. If S _v-1 = 1, then all switches are crossover connected and vice versa.

Accordingly, an area-efficient architecture having a more effective connection area than that of the conventional routing network shown in FIG. 2 can be implemented.

On the other hand, in the above example, the 16 states have been described as examples, but the present invention can be applied to a general case in which the number of non-16 states and the number of banks are changed.

5 illustrates an in-place updating technique according to an embodiment of the present invention.

In-plane updating, one of the most important techniques in path metric management, allows the removal of temporary buffers by storing output values in the position of read input values. It can be applied without any inconsistency with a scheme.

5 shows the contents of the path metric memory when the state grouping proposed in the present invention is applied with in-place updating and techniques.

As applied to the 256-state 1/3 rate Viterbi decoder used in CDMA 2000 to identify the path metric update scheme described above, Table 2 shows a comparison of the gate counts in the three types of Viterbi decoder.

block Parallel connection Using Multiplexor The present invention ACS 33,280 2,940 2,940 network 5,764 192 Traceback 537 98 98 Address generator 223 564 672 Etc 15,960 500 198 synthesis 50,000 9,366 4,100

The decoder consists of 16 ACS, 8 switches and 16 1-port memory banks. The 16 ACSs allow the decoder to process 16 states at once, so all 256 states can be processed in 16 iterations.

Although the technical idea of the present invention has been described in detail according to the above preferred embodiment, it should be noted that the above-described embodiment is for the purpose of description and not of limitation. In addition, those skilled in the art will understand that various embodiments are possible within the scope of the technical idea of the present invention.

In the conventional case, the area between the path metric memory and the add comparison selector occupies more than half of the needle size, but as described above, the present invention reduces the overall chip size by reducing the connection area by about 1/30. As a result, an excellent effect of improving the density of the Viterbi decoder can be expected.

Claims (4)

In performing state grouping of the trellis decoder using the Viterbi algorithm, A state grouping method of a trellis decoder using a Viterbi algorithm, characterized in that the memory banks are divided and the path metrics provided from the add comparison selector are alternately grouped in the divided memory banks. In a trellis decoder using the grouping method of claim 1, And a switch disposed between the add comparison selector and the bank memory to connect between the path metric memory and the add compare selector. The method of claim 2, And the switch is controlled by S _v-1 of input state encoding. The method of claim 3, wherein If S _v-1 = 1, all switches are cross-connected, and vice versa, a trellis decoder using a Viterbi algorithm.