KR100645730B1 - Interleaving Method Using Magic Matrix - Google Patents

Abstract

1. TECHNICAL FIELD OF THE INVENTION

The present invention relates to an interleaving method using a magic matrix.

2. The technical problem to be solved by the invention

An object of the present invention is to provide an interleaving method that generates an interleaving address using a magic matrix characteristic and can be easily applied at various transmission rates, and a computer-readable recording medium that records a program for realizing the method. .

3. Summary of Solution to Invention

The present invention provides an interleaving method applied to a wireless communication system, comprising: a first step of selecting a smallest frame size (N) from a value whose square size (N ² ) of the frame size is equal to or larger than the interleaver size (L); A second step of obtaining a magic matrix (N × N) using the selected frame size; A third step of reading an input value in the magic matrix and reading data in the column unit direction if the selected frame size is a predetermined multiple, and otherwise reading data input in the magic matrix in the row unit direction; And a fourth step of deleting a value larger than the selected frame size (N) to form an interleaver (I _L ) of size L.

4. Important uses of the invention

The present invention is used in a wireless communication system.

Turbo Magic Interleaver, Magic Matrix, Address, Rows, Columns

Description

Interleaving method using Magic Matrix {METHOD FOR INTERLEAVING USING MAGIC MATRIX}             

1 is an explanatory diagram of a basic magic interleaving process in an interleaving method using a magic matrix according to the present invention.

2 is an explanatory diagram of a turbo magic interleaving process according to the present invention;

3 is a block diagram of an encoding device for encoding a turbo code at a transmitting end of a wireless communication system to which the present invention is applied.

4 is a flowchart illustrating an interleaving method using a magic matrix according to the present invention.

5 shows an example of interleaving data size and deletion value.

6 is an exemplary diagram of the performance of a bit error rate (BER) according to the type of interleaver.

* Explanation of symbols for the main parts of the drawings

311 ~ 31 (n-1): Turbo Magic Interleaver

321 ~ 32n: Convolutional Encoder

The present invention strengthens the international competitiveness by opening the communication market and securing domestic technology for the turbo code adopted as the standard of Forward Error Ccorrection (FEC) in the next generation mobile communication (IMT-2000) system and developing domestic technology The present invention relates to an interleaving method using a magic matrix and a computer readable recording medium recording a program for realizing the method. More specifically, a relatively simple algorithm for generating an interleaving address by calculation is provided. The present invention relates to an interleaving method using a magic matrix and a computer readable recording medium having recorded thereon a program for realizing the method.

Recently, the research on applying the turbo code to the wireless communication system that transmits the information in the short frame such as cellular and mobile satellite system has been actively conducted, which is the data that the user wants the size of the interleaver which greatly affects the performance of the turbo code. It is shown that it is possible to apply it variably according to the type of. As the correlation of the bits encoded in the turbo code increases, more information for the decoding operation may be obtained, but the correlation of errors also increases. Therefore, the interleaver is used to remove the correlation between errors, and it is difficult to remove the degree of correlation depending on the size of the interleaver, and the complexity or delay is accompanied.

In the general channel environment, the interleaver converts a concatenation error into a random error, and the interleaver in a turbo code has a specific pattern of an input string outputting low-weight in the first component encoder through the interleaver. When it appears, the second component coder outputs a low weight parity string, which not only generates a low weight codeword as a whole, but also degrades the performance of the turbo code, thereby effectively converting correlated information into uncorrelated information. The order of the information bits is rearranged to break the error pattern. That is, when the input pattern of one Recursive Systematic Convolution (RSC) encoder gives a small distance characteristic, the permutation of the input pattern is performed so that the input pattern to the other RSC encoder can give a large distance characteristic. will be.

One factor that determines the performance of turbo code in terms of encoder is the interleaver that connects RSC codes. The larger the interleaver size, the better the performance. For short frames, it is advantageous to use the optimal structural interleaver rather than random interleaver Do. However, in the case of a long frame, since the structural interleaver is a fixed structure, it is impossible to have a minimum hamming distance of more than a predetermined size, so it is advantageous to use a random interleaver. Therefore, in order to improve the performance of the turbo code, it is necessary to use a random interleaver rather than a conventional structural interleaving method. The problem of the interleaver method is that all interleaver addresses must be stored according to respective transmission rates.

Recently, on-the-fly methods have been studied to generate an interleaver without calculating an address while maintaining the randomness of the interleaver. At this time, the interleaver address calculation algorithm can be used as an interleaver address calculation algorithm to ensure optimal performance. The linear congruential sequence (LCS) interleaver, GI (Galois Field) interleaver, MIL (Multi) stage Interleaving) Interleaver and mother interleaver. Each algorithm performs a process of optimizing parameters necessary for address calculation through a search process, and stores the obtained parameters in a read only memory (ROM) and uses them for address calculation. It is generally known that the performance of a two-dimensional array in calculating interleaver addresses is excellent. At this time, the technique used in the two-dimensional interleaver method uses a bit reversal method for the row index, and performs column permutation using an appropriate unique rule for each row. It is. Considerations in the design of the interleaver should be realized with as little memory as possible to configure the interleaver address, and should be easily applied at various data rates. Accordingly, the present invention proposes an interleaving method that generates an interleaving address by calculation and can be easily applied at various data rates with a relatively simple algorithm.

The present invention has been proposed to solve the above problems and meet the above-mentioned requirements. An interleaving method and an interleaving method that generate an interleaving address using a magic matrix characteristic and can be easily applied at various data rates. An object of the present invention is to provide a computer-readable recording medium having recorded thereon a program for realizing this.

In the method of the present invention for achieving the above object, in the interleaving method applied to the wireless communication system, the smallest frame size (N) is selected from the values of the square value (N ² ) of the frame size is equal to or larger than the interleaver size (L). A first step of making; A second step of obtaining a magic matrix (N × N) using the selected frame size; A third step of reading an input value in the magic matrix and reading data in the column unit direction if the selected frame size is a predetermined multiple, and otherwise reading data input in the magic matrix in the row unit direction; And a fourth step of deleting a value larger than the selected frame size (N) to form an interleaver (I _L ) having a size of L.

In addition, another method of the present invention for achieving the above object, in the interleaving method applied to a wireless communication system, in order to configure the interleaver ( _{N N} = row × col) of size N, in advance the number of rows and columns A first step of determining and writing an input bit string in rows; If the data in each row is replaced and the row data size (m _c ) is a predetermined multiple, the input value is filled with the magic matrix (m _c × m _c ) and then read in the column by column direction. A second step of transposing the magic matrix in a column by column direction when a size is input; A third step of shifting the data read for each row to the left in each row; And a fourth step of obtaining the row data size m _c to configure the interleaver according to the magic matrix, and reading interleaved data in column units using the configured interleaver.

In addition, another method of the present invention for achieving the above object is an interleaving method applied to a wireless communication system, the first step of determining the size of the magic interleaver (I _L ) in order to code the data into a convolution code; A second step of performing interleaving and transition using a magic matrix to generate an interleaving address; Deleting a value larger than a length of an input frame with respect to the generated interleaving address value; And a fourth step of performing interleaving using the generated interleaving address.

On the other hand, the present invention, the wireless communication system having a processor, the function of selecting the smallest frame size (N) from the value of the square value (N ² ) of the frame size or more than the interleaver size (L); Obtaining a magic matrix (N × N) using the selected frame size; Reading the data in the column unit direction after writing an input value in the magic matrix when the selected frame size is a predetermined multiple, and otherwise reading data input in the magic matrix in the row unit direction; And a computer-readable recording medium having recorded thereon a program for realizing a function of deleting a value larger than the selected frame size N, in order to configure an interleaver I _L having a size L.

In addition, the present invention, in order to form an interleaver ( _{N N} = row x col) of size N in a wireless communication system having a processor, the input bit string is determined in units of rows after determining the number of rows and columns in advance. Writing function; If the data in each row is replaced and the row data size (m _c ) is a predetermined multiple, the input value is filled with the magic matrix (m _c × m _c ) and then read in the column by column direction. Reading the magic matrix in a column by column direction by transposing the magic matrix when the size is input; Translating the data read for each row to the left in each row; A computer readable recording having a program for realizing a function of reading the row data size (m _c ) to configure the interleaver according to the magic matrix, and reading the interleaved data in units of columns using the configured interleaver. Provide the medium.

In addition, the present invention provides a wireless communication system having a processor, comprising: a function of determining a size of a magic interleaver I _{L in} order to encode data into a convolutional code; Generating interleaving addresses by performing interleaving and transition using a magic matrix; Deleting a value larger than a length of an input frame with respect to the generated interleaving address value; And a computer-readable recording medium having recorded thereon a program for realizing a function of performing interleaving using the generated interleaving address.

The above objects, features and advantages will become more apparent from the following detailed description taken in conjunction with the accompanying drawings. Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a diagram illustrating a basic magic interleaving process in an interleaving method using a magic matrix according to the present invention.

은 다음과 같이 구성된다.As shown in FIG. 1, a basic Magic Interleaver of size L

Consists of:

을 만족하는 가장 작은 N 값을 구한다.first,

Find the smallest N value that satisfies

인 매직 매트릭스(magic matrix)를 구성한다.Second, the size

Construct a magic matrix.

인터리버의 구성은 N이 4의 배수일 경우는 입력값을

매직 매트릭스(magic matrix)로 채운 다음 열 단위(column by column) 방향으로 읽어오며, 그 외는

매직 매트릭스로 입력된 데이터를 행 단위(row by row) 방향으로 읽어온다.third,

The configuration of the interleaver is an input value when N is a multiple of 4.

Fill it with a magic matrix and read it in the column by column direction.

Read the data entered in the magic matrix in the row by row direction.

을 구성하기 위하여 N보다 큰 값은 버린다.Fourth, interleaver of size L

To construct a value greater than N is discarded.

As such, the magic interleaver uses a square interleaver structure, minimizes the memory requirements for square matrix construction, and generates a look up table by a square algorithm, thus eliminating the need for a PIP (pre defined pattern). . In addition, since the sum of each row and column is uniform, the distribution of addresses is uniformly arranged.

2 is an explanatory diagram of a turbo magic interleaving process according to the present invention. Details of four steps are as follows.

First, write the input data in units of rows.

을 구성하고 최종적으로 N보다 큰 값은 버린다. 행과 열(row and column)의 수를 미리 결정하고 입력 비트열을 행(row) 단위로 쓴다.First, the input frame length is N, and the number of rows and columns is obtained by the following rule. To construct an interleaver of size N

And finally the value greater than N is discarded. Predetermine the number of rows and columns, and write the input bit string in rows.

(1) The number of columns is determined by the following rule.

Case 1: (N = 250 ~ 1000 bits) ⇒

Case 2: (N = 1001 ~ 3000 bits) ⇒

Case 3: (N = 3001∼ 8192 bits) ⇒

(2) The number of rows is determined by the following [Equation 1].

는 A보다 큰 최소 정수를 의미한다.here,

Is the minimum integer greater than A.

매트릭스에 행 단위로 입력된다.(3) The input bit string of the interleaver

It is entered in a matrix row by row.

Second, intra_row permutation is performed.

인 매직 매트릭스를 이용하여 치환(permutation)시킨다.

번째 행에 대하여 다음의 [수학식 2] 및 [수학식 3]을 이용하여 데이터들을 섞는다.(1) Shuffle the data inside each row. In other words, the size of each row of data

Permutation is performed using the in magic matrix.

For the first row, mix the data using the following [Equation 2] and [Equation 3].

, = 4의 배수

, Multiple of 4

, 그 외

, etc

값에 의한 매직 매트릭스를 이용하여

인터리버를 구성하는데, 여기서

가 4의 배수일 경우는 입력값을

매직 매트릭스로 채운 다음 열 단위(column by column) 방향으로 읽어오며, 그 외 크기의 데이터가 입력되면 매직 매트릭스를 전치(Transpose)시켜서 열 단위(column by column) 방향으로 읽어온다.That is, first in [Equation 2]

Using the magic matrix by value

Configure the interleaver, where

If is a multiple of 4, the input value is

After filling with the magic matrix, the data is read in the column by column direction. When data of other size is input, the magic matrix is transposed and read in the column by column direction.

Third, Intra_row Left Shift.

은 왼쪽으로

만큼 천이(shift)시킴을 의미한다. 즉,

번째 행(row)에 대하여

값만큼 왼쪽으로 천이시킨다. 이것은 행 별로 같은 인터리빙 패턴을 방지하기 위함이다.That is, the data read for each row is shifted to the left. In [Equation 3] above

Left

It means to shift by. In other words,

For the first row

Transition left by value. This is to prevent the same interleaving pattern for each row.

Fourth, Inter_row Permutation is performed.

In other words, the entire row is permutated as follows.

값을 구한다. 이를 구하기 위해 크기가

인 매직 매트릭스를 이용하여

인터리버를 구성하고, 이를 이용하여 열 단위(column by column)로 인터리빙된 데이터를 읽어온다.First, as shown in [Equation 4] below

Find the value. To get this,

Using the magic matrix

Construct an interleaver and use it to read interleaved data in columns by column.

값이 정수가 아니면 행보다 큰 최소 제곱수를 구하여 그의 근으로 정한다. 그리고 행보다 큰 수는 삭제(pruning)시킨다.In Equation 5 above

If the value is not an integer, the root of the least squares is determined. And pruning any number larger than the row.

번째 행에 대하여

를 이용한 어드레스 패턴을 이용하여 행 간(inter-row)을 치환하고, 최종적으로 행 단위로 데이터를 읽어온다.Equation 6 below

About the first row

Inter-rows are substituted using the address pattern using, and the data is finally read in units of rows.

번째 행 ⇒ 의 행

Second row ⇒ of

로 구성된 인터리빙 어드레스 값에 대하여 입력 프레임의 크기 N보다 큰 값은 삭제(pruning)를 한다.Finally, size L

A value larger than the size N of the input frame is pruned with respect to the interleaved address value.

3 is a block diagram of an encoding apparatus for encoding a turbo code at a transmitting end of a wireless communication system to which the present invention is applied, and shows a process of applying a magic interleaver.

First, turbo magic interleavers 311 to 31 (n-1) that reduce correlation by interleaving input transmission information bits, a convolution encoder 321 for encoding input transmission information bits, and a convolution encoder Convolutional encoders 322 to 32n for encoding the interleaved signal through the corresponding interleaver among the 311 to 31 (n-1) are provided.

As shown in FIG. 3, the transmission information bits are directly transmitted as information bits without an encoding process or encoded by convolutional encoders 321 to 32n and transmitted as parity bits. That is, the turbo magic interleaving technique using the magic matrix proposed in the interleaving process is applied.

4 is an exemplary flowchart of an interleaving method using a magic matrix according to the present invention.

As shown in FIG. 4, first, data of a transmission information bit string for interleaving is input (401) and the size of an interleaver is determined (402).

Subsequently, the data is written in the row direction and magic interleaved in each row unit to make a transition in each interior, and then magic interleaving is performed between the rows to read the data in the column direction (403).

Here, for the interleaving address value of _{L L} = row × col of size L, the value of the input frame whose size is larger than N is deleted, and then interleaving using the address of the interleaver is performed (404, 405, 406). If the size of the input frame is not greater than N, the interleaving using the address of the interleaver is performed immediately with respect to the interleaving address value _{L L} = row × col (404 and 406).

Here, the erase data values appearing during the interleaving process are shown in FIG. 5, and FIGS. 6A and 6B show the performance of the bit error rate (BER) according to the type of the interleaver.

As shown in FIGS. 6A and 6B, two convolutional encoders having a constraint length (K) = 4 and a generated polynomial of (15, 13) of a component encoder for performance analysis were used, and a code rate (R) was 1. / 3, and the size of the input frame is N = 320, 1024, assuming BPSK (Binary Phase Shift Keying) modulation and AWGN (Additive White Gaussian Noise) channel, and using a log-map algorithm The number of repetitive decoding is three.

6A and 6B, the performance of the block interleaver is the lowest, and it can be seen that the performance of the GF interleaver and the proposed interleaver of the "HNS" company is excellent. The reason why the performance is excellent is that the Hamming weight distribution characteristic is superior to other interleavers and effectively converts correlated input information into uncorrelated information within one frame.

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and various substitutions, modifications, and changes are possible in the art without departing from the technical spirit of the present invention. It will be clear to those of ordinary knowledge.

As described above, the present invention has an effect that can be easily applied at various data rates by dividing the data into an appropriate size in the interleaver data input process. In addition, the present invention has a smaller address data deletion value than other methods.

In addition, the present invention has the effect that can be implemented with as little memory as possible to configure the interleaving address in the design of the interleaver.

In addition, the present invention is simpler than the conventional turbo interleaving method, there is an effect excellent in performance.

Claims (7)

In the interleaving method applied to a wireless communication system, A first step of selecting the smallest frame size (N) among values whose square value (N ² ) of the frame size is equal to or larger than the interleaver size (L); A second step of obtaining a magic matrix (N × N) using the selected frame size; A third step of reading an input value in the magic matrix and reading data in the column unit direction if the selected frame size is a predetermined multiple, and otherwise reading data input in the magic matrix in the row unit direction; And A fourth step of deleting a value larger than the selected frame size (N) to form an interleaver (I _L ) having a size of L Interleaving method using a magic matrix comprising a. In the interleaving method applied to a wireless communication system, A first step of writing an input bit string in units of rows after determining a number of rows and columns in advance to form an interleaver having a size N (I _N = row x col); If the data in each row is replaced and the row data size (m _c ) is a predetermined multiple, the input value is filled with the magic matrix (m _c × m _c ) and then read in the column by column direction. A second step of transposing the magic matrix in a column by column direction when a size is input; A third step of shifting the data read for each row to the left in each row; And A fourth step of obtaining the row data size m _c to configure the interleaver according to the magic matrix, and reading interleaved data in column units using the configured interleaver Interleaving method using a magic matrix comprising a. In the interleaving method applied to a wireless communication system, Determining a size of the magic interleaver I _{L in} order to encode the data into a convolutional code; A second step of performing interleaving and transition using a magic matrix to generate an interleaving address; Deleting a value larger than a length of an input frame with respect to the generated interleaving address value; And A fourth step of performing interleaving using the generated interleaving address Interleaving method using a magic matrix comprising a. The method of claim 3, wherein The second step, A fifth step of determining the number of rows and columns in advance to form an interleaver (I _N = row x col) of size N and writing an input bit string in rows; If the data in each row is replaced and the row data size (m _c ) is a predetermined multiple, the input value is filled with the magic matrix (m _c × m _c ) and then read in the column by column direction. A sixth step of transposing the magic matrix in a column by column direction when the size is input; A seventh step of shifting the data read for each row to the left in each row; And An eighth step of obtaining the row data size m _c to configure the interleaver according to the magic matrix, and reading interleaved data in units of columns using the configured interleaver Interleaving method using a magic matrix comprising a. In a wireless communication system having a processor, Selecting the smallest frame size (N) from a value whose square value (N ² ) of the frame size is equal to or larger than the interleaver size (L); Obtaining a magic matrix (N × N) using the selected frame size; Reading the data in the column unit direction after writing an input value in the magic matrix when the selected frame size is a predetermined multiple, and otherwise reading data input in the magic matrix in the row unit direction; And A function of deleting a value larger than the selected frame size (N) to form an interleaver (I _L ) having a size of L A computer-readable recording medium having recorded thereon a program for realizing this. In a wireless communication system having a processor, A function of writing an input bit string in units of rows after determining a number of rows and columns in advance in order to form an interleaver (I _N = row x col) of size N; If the data in each row is replaced and the row data size (m _c ) is a predetermined multiple, the input value is filled with the magic matrix (m _c × m _c ) and then read in the column by column direction. Reading the magic matrix in a column by column direction by transposing the magic matrix when the size is input; Translating the data read for each row to the left in each row; And A function of obtaining the row data size (m _c ) to configure the interleaver according to the magic matrix, and reading interleaved data in columns by using the configured interleaver A computer-readable recording medium having recorded thereon a program for realizing this. In a wireless communication system having a processor, Determining the size of the magic interleaver I _L to encode the data into a convolutional code; Generating interleaving addresses by performing interleaving and transition using a magic matrix; Deleting a value larger than a length of an input frame with respect to the generated interleaving address value; And A function of performing interleaving using the generated interleaving address A computer-readable recording medium having recorded thereon a program for realizing this.

Images