KR100627723B1 - Parallel Decoding Method for Turbo Decoding and Turbo Decoder Using the Same - Google Patents

Abstract

The parallel decoding method for turbo decoding according to the present invention is a parallel decoding method for turbo decoding in which an input data signal is divided into a predetermined number of subblocks, and each subblock is independently processed in parallel. Repeat the decoding process as much as one repeat decoding process

The odd-numbered subblocks perform the forward state metric calculation process first and the even-numbered subblocks perform the reverse state metric calculation process first; Odd-numbered subblocks performing backward state metric calculation and even-numbered subblocks performing forward state metric calculation; And each subblock has a step of calculating an external information value.

According to the present invention, first, there is no overhead of time delay by eliminating training intervals in parallel decoding for turbo decoding. Second, the inaccuracy of the initial state metric value, which is a problem in block division, is obtained by using a boundary state metric value calculated in an adjacent block, which results in a longer training interval than the conventional algorithm. Therefore, no performance degradation occurs even with a shorter length of the subblock. The decoding delay is proportional to the length of the subblock. Thus, the present invention enables the implementation of a turbo decoder with a smaller decoding delay.

Description

Parallel decoding method for turbo decoding and a turbo decoder using the same {Parallel decoding method for turbo decoding and turbo decoder using the same}

1 is a block diagram illustrating a turbo decoder to which iterative decoding is applied.

2 is a schematic diagram showing a decoding process of a parallel block division decoding algorithm using a training interval.

3 is a schematic diagram showing a decoding process of a parallel block division decoding algorithm using a state metric value in a previous iteration.

4 is a schematic diagram for explaining a parallel decoding method for turbo decoding according to an embodiment of the present invention.

5 is a schematic diagram of a subblock showing an exchange method for using a boundary state metric as an initial state metric.

6 to 8 are results of numerical evaluation of the algorithm of the present invention and the conventional algorithm of FIG. 3 under AWGN channel environment.

9 to 13 show the results of numerical simulations by applying the algorithm of the present invention and the conventional algorithm of FIG. 3 to an IEEE 802.11a wireless LAN system in a fading channel environment.

14 is an overall block diagram of a turbo decoder designed by applying the algorithm of the present invention.

FIG. 15 is a block diagram illustrating an embodiment of an internal configuration of each sub-SISO of FIG. 14.

FIG. 16 is a block diagram illustrating an embodiment of an internal configuration of the state metric decision unit of FIG. 15.

The present invention relates to a communication system, and more particularly, to an efficient parallel decoding method for turbo decoding and a turbo decoder using the same.

Due to the rapid development of information and communication, the proportion of the multimedia wireless communication services such as data and video signals is increasing in voice-oriented services. In particular, in a multimedia communication system such as a WLAN system, a channel encoding technique having better performance is required. In such a system, when data is transmitted due to the characteristics of a wireless channel, a high probability of error occurs and loss of information occurs due to various causes such as fading, interference, and noise that may occur on the channel. Therefore, channel coding techniques used in wireless channel environments require high performance to protect the transmitted information from distortion signals (C. Berrou, A. Glavieux and P. Thitimajshima, "Near Shannon limit error correcting coding and decoding : Turbo-codes (1), "IEEE Int. Conf. On Comm.ICC '93, vol 2/3, May 1993, pp. 1064-1071.) (C. Berrou, A. Glavieux," Near Optimum Limit error -correcting coding and decoding: Turbo codes, "IEEE Trans. Commun., vol. 44, no. 10, pp. 1261-1271, 1996).

The turbo code, first proposed by Berrou [1] in 1993, consists of two relatively simple constituent coders arranged in parallel concatenation in convolution code and an interleaver with a large frame size. It has an interleaver and is said to have a very good error correction capability that is close to Shannon's limits. However, in spite of such excellent performance, turbo code has been used only for space communication due to the increased complexity due to a large amount of computation and the difficulty in real time processing due to a very long decoding delay. Recently, research has been conducted to apply a turbo code to a wireless communication system that transmits and receives information in a short packet unit such as a cellular communication or a mobile communication system.

As one of these results, a parallel block division decoding algorithm has been proposed to reduce the long decoding delay. This algorithm divides the data block into regular sub-blocks so that each subblock is processed in parallel by an independent processor, thereby reducing the decoding delay to 1 / W (where W is the number of subblocks). In parallel block division decoding algorithm, since each sub-block is processed in parallel at the same time, performance degradation occurs due to inaccuracy of initial state metric value, and a training interval can be solved (Jae-Ming Hsu and Chin and Chin-). Liang Wang, "A parallel decoding scheme For Turbo codes," IEEE Int. Symp. On Circuit and Systems, vol. 4, pp 445-448, June 1998), bounded state metric calculated during previous iterative decoding. (Seokyun Yoon, Yeheskel Bar-Ness A "Parallel MAP algorithm for low latency turbo decoding," Communications Letters, IEEE, Volume: 6, Issue: 7, July 2002). However, this algorithm has an additional time delay due to the overhead of the training interval and an additional processor due to the increase in the number of subblocks. In addition, the method of using the boundary state metric at the previous iteration may ensure the performance only when the size of the subblock is large.

Accordingly, an aspect of the present invention is to provide a method and apparatus for parallel block division decoding for turbo decoding that can reduce decoding delay time and improve decoding performance.

The parallel decoding method for turbo decoding according to the present invention for achieving the above technical problem is a parallel decoding method for turbo decoding in which an input data signal is divided into a predetermined number of subblocks and each subblock is independently processed in parallel. Repeat the decoding process as many times as the performance specification.

One iterative decoding process

(a) odd-numbered subblocks perform a forward state metric calculation process first, and even-numbered subblocks perform a reverse state metric calculation process first; (b) after step (a), odd-numbered subblocks perform reverse state metric calculation and even-numbered subblocks perform forward state metric calculation; And (c) calculating the external information value of each subblock simultaneously with the step (b).

In the step (b), the final state value of the forward state metric calculation process of the odd-numbered subblocks is determined as an initial state value of the forward state metric calculation process of the even-numbered subblocks, and the backward direction of the even-numbered subblocks is determined. The final state value of the state metric calculation process may be determined as an initial state value of the reverse state metric calculation process of the odd subblock.

The turbo decoder according to the present invention for achieving the above technical problem is a turbo decoder having a structure in which two component decoders are connected by an interleaver and a deinterleaver, and each of the component decoders independently performs a predetermined number of sub processes. In the iterative decoding process of one of a predetermined number of iterative decoding processes performed by the turbo decoder, the odd-numbered subblock first performs the forward state metric calculation process, and the even-numbered subblock is the reverse state metric calculation process. Next, the odd-numbered subblocks perform reverse state metric calculation, the even-numbered subblocks perform forward state metric calculation, and each subblock calculates an external information value. do.

The turbo decoder uses a final state value of a forward state metric calculation of the odd subblock as an initial state value of a forward state metric calculation of the even subblock, and ends the backward state metric calculation of the even subblock. The state value may be used as an initial state value of the reverse state metric calculation of the odd subblock.

Hereinafter, the configuration and operation of a turbo decoding method and apparatus by parallel block division according to a preferred embodiment of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram illustrating a turbo decoder to which iterative decoding is applied, and includes first and second soft input soft output (SISO) decoders 100 and 102, first and second interleavers 104 and 108, and a first one. And second deinterleavers 106 and 110, and hard decision unit 112.

The first SISO decoder 100 receives the received information bit (X _k, information bit), the received additional bit (Y _k , redundancy bit), and the first external information value L _a1 calculated in a previous iteration. To generate the first soft decision information L _e1 .

The first interleaver 104 rearranges the first soft decision information and outputs it as the second external information value La _a2 .

The second interleaver 108 rearranges the received information bits X _k and outputs X ^′ _k .

The second SISO decoder 102 uses the rearranged information bits X ^′ _k , the received additional bits Y _2k , and the second external information value L _a2 to determine the second soft decision information L _e2 . Create

The first deinterleaver 106 rearranges the second soft decision information L _e2 to generate the first soft decision information L _e1 , and feeds it back to the first SISO decoder.

The above-described turbo decoder performs an iterative decoding as many times as desired to obtain an output L ₂ having a required bit error rate (BER) performance.

)로서 출력된다.The second deinterleaver 110 rearranges and outputs the iterative decoding result L ₂ of the second SISO decoder 102, and the output signal is a signal quantized by the hard decision unit 112.

Is output as

Algorithms used in the first and second SISO decoders 100 and 102 generally include an algorithm using Maximum A Posteriori (MAP) and a Soft Output Viterbi Algorithm (SOVA) algorithm. Among them, the Max-Log-Map algorithm derived from MAP algorithm is easier to implement in hardware because of its superior performance and low complexity. The internal SISO decoder using the Max-Log-Map generates external information values through the state metric values generated through two processes, a forward state metric calculation (FSMC) and a backward state metric calculation (BSMC). Perform EIC (Extrinsic Information Calculation) process.

This process has a very long decoding delay because it needs to perform the FSMC after receiving the entire input data block and then perform BSMC and EIC. In order to reduce the decoding delay, a parallel decoding algorithm using several processors at the same time has been proposed. The parallel decoding algorithm is representative of the pipeline technique (C. Berrou, A. Glavieux and P. Thitimajshima, "Near Shannon limit error correcting coding and decoding: Turbo-codes (1)," IEEE Int. Conf. On Comm.ICC ' 93, vol 2/3, May 1993, pp. 1064-1071.) (Curt Schurgers, Franky Catthoor and Marc Engels, "Optimized MAP Turbo Decoder," IEEE Workshop on signal Processing Systems, pp245-254, 2000.) Parallel Decoding Algorithm (Jae-Ming Hsu and Chin and Chin-Liang Wang, "A parallel decoding scheme For Turbo codes," IEEE Int. Symp. On Circuit and Systems, vol. 4, pp 445-448, June 1998 (Seokyun Yoon, Yeheskel Bar-Ness A "Parallel MAP algorithm for low latency turbo decoding," Communications Letters, IEEE, Volume: 6, Issue: 7, July 2002).

In the pipeline technique, each processor executes the entire block and generates a result value, that is, an external information value. This can significantly reduce the decoding delay, but causes an increase in the storage medium (memory) when performing the operation, which not only causes a waste of hardware but also reduces the decoding delay.

Another method, the parallel block partitioning algorithm, divides a data block into W subblocks and decodes them in parallel using respective processors. In this algorithm, the decoding delay is reduced in inverse proportion to the number of subblocks (1 / W), but in order for each processor to be executed simultaneously, the forward state value and the reverse state value must be calculated simultaneously in each subblock, and both of them have the same value. If set, performance will be degraded due to inaccurate initial state metrics. In addition, as the length of the subblock becomes shorter than a certain size, performance decreases rapidly. To prevent this, an algorithm using the training interval and the boundary state metric of the previous iterative decoding has been proposed.

Since the parallel block division decoding algorithm using the training interval calculates the forward and backward state metrics in each block, the reliability of the initial state metric is very important, so the training interval is placed to prevent performance degradation due to the inaccuracy of the initial state value. .

2 is a schematic diagram showing a decoding process of a parallel block division decoding algorithm using a training interval T. In FIG. 2, FSMC, BSMC, and EIC mean a forward state metric calculation, a backward state metric calculation, and an external information calculation process, respectively.

When the training interval (T) does not know the initial state metric value, it takes the same initial state metric value in all subblocks, and when the state metric value is obtained, the generated state metric value can be trusted. It means that there is enough section. In general, it is known that the training interval (T) should be about 5-6 times the length of restraint.

Therefore, in this interval, each forward and backward initial state metric value starts with the same value and is accepted as a valid state metric value after the training interval (T). First, each subblock having a length of N / W + 2T (N is the length of the data block, W is the number of subblocks, and T is the length of the training interval) calculates the forward state metric value to calculate the state metric value after the training interval. After storing, the backward state metric is calculated and the external information value is calculated using the stored forward state metric and the calculated reverse state metric.

This algorithm causes performance degradation if not enough training interval T is set, and increases the decoding delay time due to the trellis overhead as much as enough training interval is set. For smaller decoding delays, the smaller the size of the subblock is, the better. However, when the length of the subblock is about 100 or less, there is a limit that the performance is degraded even with sufficient training interval. In addition, even though the same subblock length is used, more processor is required due to the portion of the training interval.

Proposed to solve this problem is a parallel block division decoding method using the state metric value in the previous iteration of FIG.

3 is an algorithm for storing boundary state metrics generated in the previous state and reusing them as initial state metrics in the next iterative decoding in order to remove the overhead of the decoding delay due to the training interval and prevent performance degradation. Since this algorithm uses the previous boundary state metric, the state metric in the previous iterative decoding increases the reliability of the initial state metric by the same effect that the training interval is equal to the subblock length. Prevents degradation.

However, this algorithm also starts with assigning the initial state metric values to the same value at the first decoding, which generates very inaccurate external information values and plays the training interval as much as the length of the previous subblock. Not enough will result in performance degradation. The length of the subblock that can be set without deterioration is about 128. Therefore, this algorithm is difficult to apply to a system that requires a small decoding delay such as wireless communication when considering repeated decoding.

The parallel block division decoding algorithms described with reference to FIGS. 2 and 3 can significantly reduce the decoding delay which is most problematic when implementing a turbo decoder, while maintaining the same performance as the initial turbo decoding scheme, but each has a certain limit. The algorithm of FIG. 2 should have a sufficient training interval and the length of the subblock, and the algorithm of FIG. 3 should use a sufficient length of the subblock to prevent performance degradation.

In order to improve the disadvantage of this performance, the present invention exchanges boundary state metrics between subblocks adjacent to each other from the first iteration, thereby eliminating training intervals and turbo decoding capable of maintaining sufficient performance even with a small subblock. Provides a parallel decoding method for. Therefore, according to the present invention, it has a very small decoding delay while maintaining satisfactory performance.

4 is a schematic diagram for explaining a parallel decoding method for turbo decoding according to an embodiment of the present invention.

The proposed structure solves the inaccuracy of the initial state metric by calculating the forward and reverse states of each adjacent subblock and providing the initial value in the next forward and reverse state metric. The state metric can be used to generate more reliable external information faster. Therefore, this structure enables the use of shorter subblock lengths without degrading performance and thus has a small decoding delay.

The parallel decoding method for turbo decoding shown in FIG. 4 is divided into six steps and described as follows.

Step 1) Divide the N signals coming into the input into W subblocks.

Step 2) Each subblock starts with a subblock starting with FSMC first and a subblock starting with BSMC first. That is, the odd-numbered subblocks perform the FSMC process first, and the even-numbered subblocks perform the BSMC process first.

At this time, the branch state metric inputted from each block is calculated and then the FSM value and the BSM value are obtained according to Equation 1, Equation 2 and Equation 3, and the result is stored to obtain an external information value. .

Where Γ _i () represents the branch metric (BM) and x ^s and x ^p are the systematic and redundancy outputs when the encoder converts from S _k to S _{k + 1} , and y ^s And y ^p are the inputs of each decoder through the channel, and L ^e _in is the external information value calculated at the previous iteration.

At this time, since the first subblock knows the starting state, it assigns the largest value to the starting state metric value and the rest to 0. Except for this, in the first iterative decoding, the initial state metric value is set to the same value, and in the second iterative decoding, the initial state metric value is assigned using the boundary state matrix value stored in the previous iterative decoding.

For example, consider any Kth and K + 1th subblocks. Kth block is A _{(K-1) M + 1} (S), A _{(K-1) M + 2} (S), A _{(K-1) M + 3} (S), ....., A _KM (S) is obtained by the equation (2). B _2KM-1 (S), B _2KM-2 (S), B _2KM-2 (S), ....., B _KM (S) in the adjacent K + 1th subblock at the same time Save it.

Step 3) In each subblock, the block that obtained the FSMC calculates the BSMC, and the block that obtains the BSMC calculates the FSMC. That is, the odd-numbered subblocks perform the BSMC process and the even-numbered subblocks perform the FSMC process. At this time, the boundary state metrics are passed to each other and used as initial state metrics. That is, the final state value of the FSMC of the odd subblock is used as the initial state value of the FSMC process of the even subblock, and the final state value of the BSMC process of the even subblock is used as the initial state value of the BSMC process of the odd subblock. Used as

For example, the Kth block is B _KM-1 (S), B _KM-2 (S), B _KM-2 (S), ........, B _{(K-1) M} (S) Is obtained from Equation 3. At the same time, the adjacent K + 1th subblock calculates A _{KM + 1} (S), A _{KM + 2} (S), A _{KM + 3} (S), ....., A _2KM (S). Where the initial B _KM (S) calculated in the process for calculating B _KM-1 (S) and A _{KM + 1} (S) is in the K + 1th, and A _KM (S) is the boundary state stored in the Kth block. Calculate using the metric.

Step 4) Simultaneously with step 3, each subblock calculates an external information value by the following equation (4).

For example, each block K and K + 1th block is L _{(d (K-1) M)} , L _{(d (K-1) M + 1)} , L _{(d (K-1) M + 2)} Calculate L _{, d2KM} .

Step 5) The external information value obtained in step 4 is input to the next decoder via an interleaver or deinterleaver, and repeated as many times as iterations from step 2. The iteration number may be determined according to the performance specification.

Step 6) Hard decision of the value of the external information as many times as the number of iterations to send the final decoded result.

This decoding process results in a longer training interval compared to the conventional algorithm of FIG. Increasing the training interval increases the reliability of the initial state metric, which improves performance. Table 1 compares the actual training intervals. In the conventional algorithm of FIG. 3, an initial state value of all sub-blocks is assigned at the first iteration, and the algorithm of the present invention uses the boundary state metric of a neighboring block as an initial state value. The training interval is equal to the length D of the subblock of. From the second iteration, the same training interval applies. Since the conventional algorithm of FIG. 3 is the same as having a training interval as much as D, when the sub-block becomes smaller, the training interval becomes smaller, resulting in a decrease in performance. However, the algorithm of the present invention makes the training interval twice as long as the conventional one and prevents performance degradation.

Subblock index Status Status Metric Training interval length at first iteration                                              Training interval length in second iterations 3 algorithm Algorithm of the Invention 3 algorithm Algorithm of the invention 2K α 0 0 D D β 0 D D 2D 2K + 1 α 0 D D 2D β 0 0 D D

5 is a schematic diagram of a subblock showing an exchange method for using a boundary state metric as an initial state metric.

The algorithm of the present invention illustrated in FIG. 4 has no performance degradation even with a relatively shorter subblock size than the conventional algorithm of FIG. 3, and the decoding delay is greatly reduced due to the shorter subblock. .

6 to 8 are results of numerical evaluation of the algorithm of the present invention and the conventional algorithm of FIG. 3 under AWGN channel environment.

The applied MAP algorithm uses Max-Log-MAP, the channel environment uses AWGN (Additive White Gaussian Noise), and the interleaver length is 1024. The number of repetitions was 4 and the code rate was 1/2. The interleaver used S-random interleaver and the number of packets was 100,000.

6, 7, and 8 are graphs of performance comparison results when the lengths of subblocks are 128, 64, and 32, respectively.

Referring to FIG. 6, according to the algorithm of the present invention, when the length of the subblock is 128, a performance gain of 0.03 dB is obtained at BER = 10 ⁻⁴ .

Referring to FIG. 7, according to the algorithm of the present invention, when the length of the subblock is 64, a performance gain of 0.08 dB is obtained at BER = 10 ⁻⁴ .

Referring to FIG. 8, according to the algorithm of the present invention, when the length of the subblock is 32, a performance gain of 0.17 dB is obtained at BER = 10 ⁻⁴ .

Although not shown, according to the algorithm of the present invention, when the length of the subblock is 16, a performance gain of 0.32 dB is obtained at BER = 10 ⁻⁴ . However, when the length of the subblock is 16, BER = 10 ^-4 has a sharp increase in SNR as 2.2dB, resulting in a performance degradation. The algorithm of the present invention can have a length of up to 32 subblocks.

It can be seen that the algorithm of the present invention shows superior performance when the length of the subblock is smaller than 128 compared with the conventional algorithm. Comparing the performance when the length of the subblock is 32, 64, 128, it can be seen that the performance of both algorithms is about 128, but the performance of the existing algorithm is lower than that of the proposed algorithm. While the conventional algorithm has a minimum subblock length of 128 that can be used without degrading performance, the algorithm of the present invention can have a subblock length of 32.

Table 2 below shows the performance gains of the algorithm of the present invention.

Subblock length Algorithm (dB) of FIG. 3 Algorithm of the Invention (dB) Performance Gain (dB) (BER = 10 ^-4 ) 16 2.52 2.20 0.32 32 2.25 2.08 0.17 64 2.12 2.04 0.08 128 2.05 2.02 0.03 256 2.03 2.02 0.01 Full Size 2.02 2.02 -

If the length of the subblock is more than 128, there is little performance difference, but there is a performance gain of 0.08dB at 64, 0.17dB at 32, and 0.32dB at 16. In addition, it can be seen that the performance of the subblock 32 of the algorithm of the present invention is substantially the same as the performance of the subblock 128 of the conventional algorithm. This means that it is possible to apply a quarter length subblock to the conventional algorithm to reduce the time delay. Since the decoding delay is proportional to the length of the subblock, reducing the length of the subblock by 1/4 is equivalent to reducing the decoding delay by 75%.

Table 3 compares the decoding delays of the algorithm of the present invention and the conventional algorithms.

algorithm Common MAP Algorithm Fig. 3 algorithm Algorithm of the invention Subblock length without degradation - 128 32 Minimum decoding delay without performance degradation (ex) N = 1024 O (N) = 1 O (N / W) = 1/8 O (N / W) = 1/32

Using a subblock with a short block length to reduce the decoding delay causes performance degradation. Therefore, the minimum length of subblock possible without degrading performance determines the decoding delay of the algorithm. Table 3 compares the minimum decoding delay that the algorithm can determine. O (·) is a function of decoding delay and is proportional to the parameter (·). In general turbo decoding, since the FSM and BSM of the entire block are obtained and EI is obtained, the decoding delay function is determined as a function of the length N of the entire data block, whereas the conventional decoding algorithm and the algorithm of the present invention use L (= N / W). Determined by a function If the decoding delay function O (N) is assumed to be 1, the decoding delay of the conventional algorithm and the algorithm of the present invention is 1 / L. At this time, when the decoding delays of the respective algorithms are compared with the length of the minimum sub-block without degrading performance, when N = 1024, it becomes 1/8 according to the conventional algorithm of FIG. 3 and 1/32 according to the algorithm of the present invention. As a result, the algorithm of the present invention can reduce the decoding delay of the conventional algorithm by about 75%.

In order to verify the algorithm of the present invention at the system level, performance evaluation was performed by applying to an IEEE 802.11a wireless LAN system.

9 to 13 show the results of numerical simulations by applying the algorithm of the present invention and the conventional algorithm of FIG. 3 to an IEEE 802.11a wireless LAN system in a fading channel environment.

The IEEE 802.11 standardization group has established IEEE 802.11a, a high-speed wireless LAN system standard of OFDM method that can transmit data of 6 to 54Mbps in the 5GHz band. The system supports variable frame lengths and various code rates based on OFDM to achieve various data rates.

Table 4 summarizes the parameters of the turbo decoder to be applied to the IEEE 802.11a WLAN system.

parameter value Turbo Decoding Ratio 1/2, 2/3, 3/4 Interleaver size 216 Subblock length 18, 30, 45, 60, 108 Generator Polynomial (13, 15) ₈ Restraint 4 Repeat count 4 Interleaver Type S-random interleaver SISO Decoder Max-Log-MAP

As shown in Table 4, the algorithm of the internal decoder uses the S-random interleaver, which is known to reduce the complexity of the hardware by using Max_Log_Map and excellent performance. The interleaver length and the number of iterations were determined by simulation in consideration of the performance and hardware complexity.

Since the IEEE 802.11a wireless LAN system is packet-based communication, the performance is compared by PER. The simulation environment is a fading channel, 64QAM, 3/4 code rate, 50,000 packets. The experimental results compare the performance in the fading channel, which is a worse channel environment than the AWGN channel.

9 to 13 are graphs of performance comparison results when the lengths of subblocks are 108, 60, 45, 30, and 18, respectively.

Referring to FIG. 9, according to the algorithm of the present invention, when the length of the subblock is 108, a performance gain of 0.2 dB is obtained at PER = 10 ⁻² .

Referring to FIG. 10, according to the algorithm of the present invention, when the length of the subblock is 60, a performance gain of 0.7 dB is obtained at PER = 10 ⁻² .

Referring to FIG. 11, according to the algorithm of the present invention, when the length of the subblock is 45, a performance gain of 0.8 dB is obtained at PER = 10 ⁻² .

Referring to FIG. 12, according to the algorithm of the present invention, when the length of the subblock is 30, a performance gain of 1.7 dB is obtained at PER = 10 ⁻² .

Referring to FIG. 13, according to the algorithm of the present invention, when the length of the subblock is 18, a performance gain of 1.9 dB is obtained at PER = 10 ⁻² . However, when the length of the subblock is 18, the SNR at PER = 10 ^-2 is rapidly increased to 20.6 dB, resulting in a performance degradation. The algorithm of the present invention can have a length of up to 30 subblocks.

Table 5 shows the results of comparing and evaluating the performance of the algorithm of the present invention in the IEEE 802.11a wireless LAN system.

Subblock length Conventional Algorithm (dB) Algorithm of the Invention (dB) Performance Gain (dB) (PER = 10 ^-2 ) 18 22.5 20.6 1.9 30 21.5 19.8 1.7 45 20.5 19.7 0.8 60 20.2 19.5 0.7 108 19.6 19.4 0.2 Full Size 19.4 19.4 -

When the length of the subblock is 18, a performance gain of 1.9 dB is obtained compared to the conventional algorithm, and a performance gain of 1.7 dB in 30, 0.8 dB in 45, 0.7 dB in 60, and 0.2 dB in 108 is obtained. It can be seen that the shorter the length of the subblock, the worse the performance. Comparing performance with the case of no block division, the conventional algorithm should have a subblock length of 100 or more and the algorithm of the present invention should be 30 or more. In view of the decoding delay, the conventional algorithm 108 and the algorithm 30 of the present invention exhibit almost the same performance. Therefore, when the minimum subblock length is used without deterioration, the algorithm of the present invention achieves the decoding delay like the experimental results in AWGN. It can be reduced by 70%.

14 is a block diagram of a turbo decoder designed by applying the algorithm of the present invention, including a control unit 100, an input buffer 102, eight SISO blocks 104-1 to 104-8, and four interleavers 106-. 1 to 106-4, four deinterleavers 108-1 to 108-4, a hard decision unit 110, an output buffer 112, and a ROM address generator 114.

The turbo decoder of FIG. 14 performs one iteration per two SISO blocks, one interleaver, and one deinterleaver under the control of the control unit 100 to control the signal input through the input buffer 102 to perform four iterations in total. Perform. At this time, the data arrangement and rearrangement of each interleaver and deinterleaver are performed under the control of the ROM address generator 114.

Each SISO block has sub-SISO0 to sub-SISO7 serving as a processor. Between each sub-SISO, there is a register (not shown) that can transfer each boundary state metric value, so that adjacent sub-SISO blocks transmit boundary state metric values between adjacent sub-SISO blocks. When the interleaver and the deinterleaver are implemented in the S-random type, the interleaver and the deinterleaver store the address value generated in advance in the ROM address generator 114 and refer to the address value when reading the stored external information value. The turbo decoder of FIG. 14 uses the pipeline structure as a whole for iterative decoding. This structure increases the complexity of the hardware, but enables high throughput by allowing the continuous decoding of variable frames in wireless communication and the like. Eight SISOs are connected in series for four iterative decoding.

FIG. 15 is a block diagram illustrating an example of an internal configuration of each sub-SISO of FIG. 14, and includes a branch metric determining unit 200 and a state metric determining unit 202.

The branch metric determiner 200 determines the branch metric BM based on the systematic data DATA_sys, the additional data Data_re, and the external information value EI _i-1 of the previous iteration.

The state metric determiner 202 is a branch metric (BM), the systematic data (DATA_sys), the external information value (EI _i-1 ) of the previous iteration, the forward initial state metric (Initial_FSM), the reverse initial state metric (Initial_BSM) The external information value (EI _i ), the final forward state metric (Final_FSM), and the final reverse state metric (Final_BSM) are determined by receiving the value.

FIG. 16 is a block diagram illustrating an example of an internal configuration of the state metric determining unit of FIG. 15. The forward state metric calculating unit 300, the reverse state metric calculating unit 302, the storing unit 304, and the external information value calculating unit are illustrated. 306.

The forward state metric calculator 300 receives the branch metric BM and the forward initial state metric (Initial_FSM), calculates the forward state metric (FSM), and outputs the final forward state metric (Final_FSM) when the last iteration is completed.

The reverse state metric calculation unit 302 receives the branch metric BM and the reverse initial state metric B_, calculates the reverse state metric BSM, and outputs the final reverse state metric Final_BSM when the last iteration is completed.

The storage 304 stores the forward state metric (FSM) while calculating the reverse state metric.

The external information value calculator 306 receives the forward state metric (FSM), the reverse state metric (BSM), the systematic data (DATA_sys), and the external information value (EI _i-1 ) of the previous iteration. _i )

In the sub-SISOs shown in FIGS. 15 and 16, the order in which FSMs and BSMs are calculated in odd and even numbers is reversed. That is, in one iterative decoding process from the initial state, the odd subblock performs the forward state metric calculation process first and the even subblock performs the reverse state metric calculation process first. Then, the odd-numbered subblocks perform the backward state metric calculation and the even-numbered subblocks perform the forward state metric calculation.

The parallel decoding method for turbo decoding according to the present invention can be implemented as computer readable codes on a computer readable recording medium. Computer-readable recording media include any type of recording device that stores programs or data that can be read by a computer system. Examples of computer-readable recording media include ROM, RAM, CD-ROM, magnetic tape, hard disk, floppy disk, flash memory, optical data storage, and the like. Here, the program stored in the recording medium refers to a series of instruction instructions used directly or indirectly in an apparatus having an information processing capability such as a computer to obtain a specific result. Thus, the term computer is used to mean all devices having an information processing capability for performing a specific function by a program, including a memory, an input / output device, and an arithmetic device, regardless of the name actually used.

In addition, the parallel decoding method for turbo decoding according to the present invention is an integrated circuit which can be programmed in a schematic or ultra-high speed integrated circuit hardware description language (VHDL, Verilog-HDL, etc.) on a computer, and connected to a computer and programmable. For example, it may be implemented by a field programmable gate array (FPGA). In addition, the recording medium is a concept including such a programmable integrated circuit or ASIC (application specific integrated circuit).

The best embodiments have been disclosed in the drawings and specification above. Although specific terms have been used herein, they are used only for the purpose of describing the present invention and are not used to limit the scope of the present invention as defined in the meaning or claims. Therefore, those skilled in the art will understand that various modifications and equivalent other embodiments are possible from this. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

As described above, according to the parallel decoding method for turbo decoding and the turbo decoder using the same, the following effects can be obtained.

First, there is no overhead of time delay by eliminating training intervals in parallel decoding for turbo decoding.

Second, the inaccuracy of the initial state metric value, which is a problem in block division, is obtained by using a boundary state metric value calculated in an adjacent block, which results in a longer training interval than the conventional algorithm. Therefore, no performance degradation occurs even with a shorter length of the subblock. The decoding delay is proportional to the length of the subblock. Thus, the present invention enables the implementation of a turbo decoder with a smaller decoding delay.

As a result of designing a turbo decoder suitable for a wireless LAN system using the decoding method of the present invention, the decoding delay can be reduced by 70% while maintaining the same performance as a conventional turbo decoder.

The invention is not limited to the examples described above and represented in the drawings. Those skilled in the art taught by the above-described embodiments, many modifications to the above-described embodiments are possible by substitution, erasure, merging, etc. within the scope and object of the present invention described in the following claims.

Claims (9)

A parallel decoding method for turbo decoding in which an input data signal is divided into a predetermined number of subblocks, and each subblock is independently processed in parallel. Repeat the decoding process a predetermined number of times according to the performance specification, One iterative decoding process (a) odd-numbered subblocks perform a forward state metric calculation process first, and even-numbered subblocks perform a reverse state metric calculation process first; (b) after step (a), odd-numbered subblocks perform backward state metric calculation and even-numbered subblocks perform forward state metric calculation; And (c) parallel to the step (b), wherein each subblock comprises calculating an external information value. The method of claim 1, wherein step (b) The final state value of the forward state metric calculation process of the odd subblock is determined as an initial state value of the forward state metric calculation process of the even subblock. And determining a final state value of a reverse state metric calculation process of the even subblock as an initial state value of a reverse state metric calculation process of the odd subblock. The method of claim 1, wherein the size of the subblock is Parallel decoding method for turbo decoding characterized in that less than 128 in AWGN channel environment. The method of claim 1, wherein the size of the subblock is Parallel decoding method for turbo decoding, characterized in that more than 32 in the AWGN channel environment. The method of claim 1, wherein the size of the subblock is Parallel decoding method for turbo decoding, characterized in that less than 108 in the WLAN system. The method of claim 1, wherein the size of the subblock is Parallel decoding method for turbo decoding, characterized in that more than 30 in the WLAN system. In a turbo decoder having a structure in which two component decoders are connected by an interleaver and a deinterleaver, each of the component decoders includes a predetermined number of subblocks for performing parallel processing independently. In one iterative decoding process of a predetermined number of iterative decoding processes performed by the turbo decoder, Odd-numbered subblocks perform forward state metric calculation first, and even-numbered subblocks perform reverse state metric calculation first. Next, the odd-numbered subblocks perform a reverse state metric calculation process, the even-numbered subblocks perform a forward state metric calculation process, and each of the subblocks calculates an external information value. The method of claim 7, wherein Using the final state value of the forward state metric calculation of the odd subblock as an initial state value of the forward state metric calculation of the even subblock, And a final state value of a reverse state metric calculation of the even subblock is used as an initial state value of a reverse state metric calculation of the odd subblock. A computer-readable recording medium having recorded thereon a program for executing the method of any one of claims 1 to 6.

Images