KR101991447B1 - The Method of Protograph LDPC codes Construction Robust to Block Interference and Fading - Google Patents

Abstract

The present invention relates to LDPC code design techniques. A high code rate protograph-based LDPC code design scheme robust to block interference and block fading according to the present invention includes: calculating a structure of a base matrix that prevents a codeword from being generated in one hop; Calculating an optimized basis matrix through a PEXIT algorithm in which a value of a position corresponding to one hop among channel initial values is modified; Deriving a parity check matrix through lifting from the calculated basic matrix; And designing an LDPC decoder and an encoder that follow the parity check matrix.

Description

[0001] The present invention relates to a high-rate protocol graph-based LDPC code design technique robust against block interference and block fading,

The present invention relates to LDPC code design techniques.

The block interference channel model is a channel model with a very long bit-length cluster error called a block in one frame. The channel interference model is based on the previous paper 1 (R. McEliece and WE Stark, "Channels with block interference," IEEE Trans. (GE) model for modeling a land mobile satellite channel (LMSC) or partial band jamming in a frequency hopping environment As a modeling tool. In order to improve the performance of existing error correcting codes in a block interfering channel, a sufficiently long interleaver relative to the unit code length is required, which causes high design complexity and delay.

In order to improve this, the prior art 2 (L. Wilhelmsson and LB Milstein, "On the effect of imperfect interleaving for the Gilbert-Elliott channel," IEEE Trans. Commun., Vol.47, no.5, pp. 681-688, May 1999.) introduced the imperfect interleaver considering the Marcov probability process of the GE model and improved the performance to the same level as the infinite length interleaver. However, the method which is still dependent on the interleaver is inevitably very complicated and delayed by the decoding process of the unit error correcting code.

In order to overcome this disadvantage, it is conceivable to modify the code structure design so that the unit error correcting code can be decoded in the block interfering channel. Low-density parity-check (LDPC) codes among various error correction coding schemes are the next generation codes used in communication techniques such as IEEE 802.16e or DVB-S2 and ATSC 3.0. Due to the freedom of design, fading channels and block error channels Optimized design techniques for various channels have been proposed.

The LDPC code is represented by a graph in which variable nodes and check nodes are interconnected and a corresponding parity check matrix. The coding performance of the LDPC code is determined according to the connection relationship of the two node graphs.

The theoretical performance analysis of LDPC codes basically uses density evolution (DE), which is a probabilistic technique, and it is also possible to design optimal LDPC codes by using code design using probability distributions of variable nodes and check nodes having high performance in density evolution Can be obtained. However, the LDPC code design proposed in the communication standard and system uses a representation and a method called a protograph.

The protograph-based LDPC code is advantageous in that it can utilize a low-complexity algorithm compared to the LDPC code based on the probability technique in the design process, encoding and decoding process. In most cases including the communication standard mentioned above .

A protograph or a base matrix of a protograph-based LDPC code is represented by a reduced form of a node graph or a parity check matrix, which is a concept of an existing LDPC code, and a protograph ) Or base matrix is determined, a final LDPC code is determined through a series of lifting processes. In the protograph-based LDPC code, a technique called protext extrinsic information transfer (PEXIT), which can be utilized in the base matrix, is utilized for the theoretical performance analysis. Lifting by selecting a specific base matrix, It is known that the LDPC codes of the present invention exhibit high performance.

The block fading model has many similarities with the block interference model, and many studies exist as a channel model adopted in a multi-frequency environment, a frequency hopping environment, and an orthogonal frequency division multiplexing (OFDM) environment.

In this paper, we propose a novel LDPC coding scheme for improving the performance of LDPC codes. In this paper, we propose a new LDPC code, The root LDPC code for the block fading environment has been proposed for the first time in the IEEE Trans. Inf. Theory, vol.56, no.9, pp. 4286-4300, Sep. 2010. The protograph- (Y. Fang, G. Bi, and YL Guan, "Design and analysis of root-protograph LDPC codes for non-ergodic block-fading channels," IEEE Trans. Wireless Commun., Vol.14, no.2, pp. 738-749, Sep. 2014.).

The characteristics of the LDPC code for block fading mentioned above have low code rates, show high performance even in a large number of degraded block environments, and have similar results in a block interference model, which is a similar model. The problem is that the frequency of interference occurring in the block interference model is low, and the performance guaranteed by the error correcting code used in the block fading is very high as compared with the channel environment. However, the conventional method operates at a too low code rate, .

Therefore, it is necessary to design a new LDPC code that utilizes the principle of high code and root LDPC code that can operate efficiently when the frequency of interference generated in the block interference model is low. Also, when these codes are designed based on a protograph, there is an advantage that the theoretical performance analysis is easy and the design complexity is reduced and practicality is enhanced.

The present invention is directed to solving the above-mentioned problems and other problems. Another object of the present invention is to provide a high-rate protograph-based LDPC code design technique robust against block interference and block fading.

According to an aspect of the present invention, there is provided a method of generating a structure of a base matrix that prevents a codeword from being generated within a hop; Calculating an optimized basis matrix through a PEXIT algorithm in which a value of a position corresponding to one hop among channel initial values is modified; Deriving a parity check matrix through lifting from the calculated basic matrix; And designing an LDPC decoder and an encoder according to the parity check matrix. The high-rate protograph-based LDPC code design technique is robust against block interference and block fading.

In an embodiment, the size of the base matrix may be determined by a parameter that affects the number of hops (L) and the coding rate.

In another embodiment, the basic matrix may be composed of a partial matrix corresponding to each hop.

The effect of the high code rate protograph-based LDPC code design technique robust to block interference and block fading according to the present invention is as follows.

The conventional technique, which includes a low-code-rate root LDPC code base to make full diversity, utilizes parity more than necessary when the frequency of interference generated in the block interference model is low.

According to at least one of the embodiments of the present invention, a protograph-based LDPC code design method that is close to the optimized performance that can be theoretically obtained when the frequency of interference is low is proposed. To design the proposed code, a base matrix of a specific structure is assumed, and a modified PEXIT algorithm is used to specify a specific value of the base matrix.

The simulation results show that the proposed code has better performance than the regular LDPC code used at the same coding rate.

Further scope of applicability of the present invention will become apparent from the following detailed description. It should be understood, however, that the detailed description and specific examples, such as the preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art.

FIG. 1 is a block diagram for explaining an embodiment of a frequency hopping system with high frequency efficiency proposed according to the present invention.
2 is a conceptual diagram for explaining a frame structure and a packet error rate of a system designed according to the present invention.
3 is a flowchart of a modified PEXIT algorithm.
4 is a conceptual diagram for explaining the superiority of a block interfering channel of a basic matrix proposed according to the present invention.
FIG. 5 is a flowchart for explaining an embodiment of a process of designing a final parity check matrix, an LDPC encoder and a decoder from the proposed basic matrix and PEXIT algorithm.
Figure 6 is an embodiment of a basic matrix designed by the proposed method according to the present invention.
FIG. 7 is a graph for explaining a frame error rate change of a proposed LDPC code and a normal LDPC code due to block interference when fading does not exist.
8 is a graph for explaining a change in a frame error rate of a proposed LDPC code and a normal LDPC code due to block interference when Rayleigh fading is present.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings, wherein like or similar components are denoted by the same reference numerals, and redundant explanations thereof will be omitted. The suffix "module" and " part "for the components used in the following description are given or mixed in consideration of ease of specification, and do not have their own meaning or role. In the following description of the embodiments of the present invention, a detailed description of related arts will be omitted when it is determined that the gist of the embodiments disclosed herein may be blurred. It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed. , ≪ / RTI > equivalents, and alternatives.

Terms including ordinals, such as first, second, etc., may be used to describe various elements, but the elements are not limited to these terms. The terms are used only for the purpose of distinguishing one component from another.

It is to be understood that when an element is referred to as being "connected" or "connected" to another element, it may be directly connected or connected to the other element, . On the other hand, when an element is referred to as being "directly connected" or "directly connected" to another element, it should be understood that there are no other elements in between.

The singular expressions include plural expressions unless the context clearly dictates otherwise.

In the present application, the terms "comprises", "having", and the like are used to specify that a feature, a number, a step, an operation, an element, a component, But do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, or combinations thereof.

Hereinafter, the present invention will be described in more detail with reference to the accompanying drawings. In the following description, all embodiments of the present invention are not disclosed. The invention may be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. These embodiments are provided to satisfy legal requirements for application. Like reference numerals are used throughout the same components.

LDPC 부호가 사용된다. 일반적인 통신 규격에서는 인터리버 및 스크램블러 등이 활용되나, 이 부분이 제안하는 오류 정정 부호의 성능에 영향을 주지는 않으므로, 본 발명에서는 이들이 제외된 단순화된 시스템 모델을 사용한다. 블록 페이딩이 포함된 구체적인 시스템의 블록 다이어그램은 도 1과 같이 표현된다. In the present invention, it is assumed that a slow frequency hopping environment is assumed, and block interference occurs in units of hop, which is a unit of hopping. BPSK modulator / demodulator is used as modulation / demodulation method, protograph-based error correction code

An LDPC code is used. An interleaver and a scrambler are used in a general communication standard, but since this portion does not affect the performance of the error correcting code proposed in the present invention, the simplified system model excluding the interleaver and the scrambler is used in the present invention. A block diagram of a specific system including block fading is represented as in FIG.

FIG. 1 is a block diagram for explaining an embodiment of a frequency hopping system with high frequency efficiency proposed according to the present invention.

Referring to FIG. 1, the system can be roughly divided into three categories: a transmitter, a channel model, and a receiver.

비트로 이루어진 메시지 비트 m은 LDPC 부호기에 의해

비트로 부호화되며 이 단위를 프레임이라고 부른다. 그 뒤, BPSK 변조기에 의해 변조가 수행된다. 변조 후의 값은 성좌도(constellation)에 의해 결정된 특정 위상 값을 지닌 파형으로 대응되며, 주파수 hopper에 의해 홉(hop)이라고 불리는 부분적인 다수의 비트 단위로 기저 대역으로부터 단일 주파수 대역으로 전송된다. At the transmitter

The message bit m composed of bits is encoded by the LDPC encoder

Bit, and this unit is called a frame. Subsequently, modulation is performed by a BPSK modulator. The value after modulation corresponds to a waveform having a specific phase value determined by a constellation and is transmitted from the baseband to a single frequency band on a partial multiple bit basis called a hop by a frequency hopper.

로 신호 대 잡음 세기 비율을 나타낸다. In the channel model, a frame error occurs due to random errors in the channel of Gaussian distribution in a bit unit and block interference occurring in a hop unit of a certain probability. The parameters that affect random error occurrence are

To-noise ratio.

The probability that a block interference of a hop unit occurs is ρ , and when an interference occurs, a bit of the hop is assumed to be a random pattern independent of the existing value, so that all existing information is lost.

If other models include block fading, this also affects performance. In general communication, the phenomenon called fading affects the overall area of the signal, such as signal strength and phase, but in this model, it is assumed that the signal strength changes only by fading.

에 대해 페이딩 계수

만큼 변한다고 가정한다. 이 경우 채널 정보는 신호 및 잡음 비, 블록 간섭 여부 및 페이딩 계수로 간주하며, 수신기는 앞서 언급한 채널 정보를 확보할 수 있다고 가정한다. Block fading occurs in units of hop, and the index of each hop

The fading coefficient

. In this case, the channel information is regarded as signal and noise ratio, block interference, and fading coefficient, and it is assumed that the receiver obtains the channel information mentioned above.

에 계산을 위해서는 채널 정보인 페이딩 계수

및 가우시안 분포의 분산

을 활용하며, 각 비트의 정렬된 위상에서의 전력값을

라고 할 때, 다음의 수학식 1을 따른다.In the receiver, the hop of a specific frequency band is shifted as a baseband through a frequency dehopper. The demodulator determines the position of the constellation corresponding to the transmitted waveform, and provides a soft-decision log-likelihood ratio (LLR) based on it. LLR value

The channel information, the fading coefficient

And variance of Gaussian distribution

, And the power value in the aligned phase of each bit

, The following equation (1) is obtained.

The LDPC decoder performs decoding through belief propagation (BP) from the soft-decision LLR value received from the demodulator to recover the original message.

The design technique of the LDPC code which is a main part of the present invention is as follows.

로, 높은 부호율을 지니고 있으며, 설계 방법의 핵심은 하나의 홉 내에 생길 수 있는 부호어가 존재하지 않도록 하는 구조로 기초 행렬이 도 2와 같은 구조가 되도록 설계한다. The code rate of this LDPC code is

, And has a high coding rate. The core of the design method is to design a base matrix such that the base matrix has a structure as shown in FIG. 2, such that there is no codeword that can occur in one hop.

2 is a conceptual diagram for explaining a frame structure and a packet error rate of a system designed according to the present invention.

의 크기로

은 홉의 개수,

는 설계 파라미터로 특히

는 부호율에 영향을 준다. 각 홉의 경우

개의 열 위치에 대응되며, 그 행렬은 각 대각 요소(diagonal element)가 1이며 열 하단 삼각형식(lower triangular form) 혹은 상단 삼각형식(upper triangular form)의 행의 중간 행이 직사각 형태의 특정 0이 아닌 값이 삽입될 수 있는 구조를 따른다. 또한, 이러한 삼각형식의 직사각 형태의 구조는 각 홉마다 다른 위치를 지니며, 전체적으로 각 검사 행렬의 계수가 일정하게 유지되도록 설계한다. Referring to FIG. 2, the size of the base matrix is

In the size of

The number of hops,

As a design parameter

Affects the coding rate. For each hop

The matrix corresponds to a column position where each diagonal element is 1 and a middle row of rows in a lower triangular form or an upper triangular form has a specific zero of a rectangular shape Followed by a structure where non-values can be inserted. In addition, the triangular-shaped rectangular-shaped structure has different positions for each hop, and the coefficients of the respective check matrices are designed so as to be constant as a whole.

The specific design method is as follows.

이며, 대각 요소가 1인 어떤 상단 혹은 하단 삼각 형식

행렬 및 크기가

인

행렬을 생각할 수 있다. The size

, And any upper or lower triangular format with a diagonal element of 1

Matrix and size

sign

You can think of a matrix.

에 대해, 각 홉에 위치하는 부분 행렬(submatrix)

로 구성되도록 한다. 또한, 상단 삼각 형식에서 결정되지 않는 값은 변형된 PEXIT 알고리즘을 통해 해당하는

에 복호 성공 및 실패를 예측하며, 미 결정된 값 중 가능한 모든 음수가 아닌 정수 조합에 대해 중 복호가 성공하는

중 최소의 값으로 나타나는 조합으로 결정한다. In that case,

(Submatrix) located in each hop,

. In addition, values that are not determined in the upper triangular format are determined by the modified PEXIT algorithm

And decides success or failure of decryption, and if the decryption succeeds for all non-negative integer combinations among the undetermined values

The minimum value is determined by the combination of the values.

A flowchart of the modified PEXIT algorithm is shown in FIG.

3 is a flowchart of a modified PEXIT algorithm.

In the PEXIT algorithm presented in the previous issue 5 (L. Gianluigi and M. Chiani, "Protograph LDPC codes design based on EXIT analysis," GLOBECOM, Washington DC: USA, 2007, pp. 3250-3254) Share the proposed mathematical definitions and expressions. The difference is that the value of the position corresponding to one hop among the channel initial values is modified to enable asymptotic analysis even in the case of block interference.

Referring to FIG. 3, a fading coefficient of the first hop is set to 0, and a fading coefficient of the other hop is set to a channel value based on the standard deviation of the Gaussian noise.

Then, a step of updating the mutual information value of the variable and the check node in the photographed relationship is proceeded.

The variable node is the position of the codeword, and the check node is the vertex of the protograph expressed as a syndrome which is a linear constraint that each codeword should satisfy, and can be updated according to the mutual connection relationship of the graph.

The step of deriving the accumulated mutual information value of each variable node determined by the channel value is then proceeded.

The cumulative mutual information value is calculated by using information entropy for reliability of each codeword value during the decoding process. The cumulative mutual information value has a value between 0 and 1, and the closer the value is, the more reliable the decoded codeword value is.

Next, if the cumulative mutual information value of all the variable nodes is 1 and the decoding of the corresponding protograph structure is successful or the maximum number of iterations is repeated, It is determined that the decoding of the corresponding protograph structure has failed.

The asymptotic performance of the corresponding average LDPC code from the specific Eb / N0 and protograph can be obtained through the decoding success or failure of the PEXIT algorithm, and the finite length decoding performance is highly correlated with the asymptotic performance by the PEXIT algorithm have.

이며

인 경우, 도 4와 같은 기초 행렬 및 대응되는 프로토그래프가 있다고 가정할 수 있다. The reason why this design exhibits excellent performance in the proposed channel condition can be seen from the protograph corresponding to the base matrix. 2,

And

, It can be assumed that there is a basic matrix and a corresponding protograph as shown in FIG.

4 is a conceptual diagram for explaining the superiority of a block interfering channel of a basic matrix proposed according to the present invention.

Such a protograph expresses the number of interconnection relations as elements of each matrix, with check nodes as rows, variable nodes as columns. First, the second check matrix has a connection relation with a variable node belonging to the first hop, the first variable node, and a connection relation from other hops. The third check matrix has the same connection relation as the first check node except for the possible connection relationship with the first variable node having only one connection relation with the second check node.

For example, if the check matrix maintains only one connection in a certain hop, or excludes the connection with a variable node having a connection with a check node satisfying the condition, if there is only one connection relation, As rootcheck.

Rootcheck is a useful structure for solving block interference, which can be illustrated by the example represented in FIG. 4, if block interference occurs in the first hop, even if the reliability of the first variable node itself is low by the second check node, block interference does not occur. Therefore, only the LLR value It is easy to correct the interference value. The second variable node also obtains the LLR value only from the first corrected node and the other highly reliable variable node, so that interference correction is easy. This correction process is designed so that even if the block interference occurs in another hop, the basic matrix is designed to be corrected through a similar process.

FIG. 5 is a flowchart for explaining an embodiment of a process of designing a final parity check matrix, an LDPC encoder and a decoder from the proposed basic matrix and PEXIT algorithm.

Referring to FIG. 5, each element of the determined basic matrix corresponds to a matrix such as a circulant matrix. In this case, the PEG is used to determine a circulant value. Such a process is called lifting, and the corresponding parity check matrix can be used to form a decoder or an encoder.

,

및 부호율

인 경우, 제안된 행렬 구조 및 변형된 PEXIT를 통해 행렬 원소를 각각 얻어진 최종적인 기초 행렬은 도 6와 같다. The proposed design is designed to be able to design the number and parameters of various hops, but we will refer to one example that can confirm the superiority.

,

And code rate

, The final matrix obtained by respectively obtaining the matrix elements through the proposed matrix structure and the modified PEXIT is as shown in FIG.

Figure 6 is an embodiment of a basic matrix designed by the proposed method according to the present invention.

인 경우에서 이를 부호 길이가 2304인 제안 부호와 일반적인 정규 (3,9) LDPC 부호의 프레임 오류율 (FER, frame error rate)은 페이딩이 없는 경우 (도 7) 및 레일리 페이딩이 존재하는 경우 (도 8)와 같다. The final parity check matrix was obtained by using the circulant - based and PEG algorithm so that the girth from the base matrix was 8 or more. As the assumption of the block interference channel, the channel information is acquired from the receiver and the probability of block interference

The frame error rate (FER) of the proposed normal code (3,9 LDPC code) with the code length of 2304 in the case of no fading (FIG. 7) and the case of Rayleigh fading (FIG. 8 ).

FIG. 7 is a graph for explaining a frame error rate change of a proposed LDPC code and a normal LDPC code due to block interference when fading does not exist.

8 is a graph for explaining a change in a frame error rate of a proposed LDPC code and a normal LDPC code due to block interference when Rayleigh fading is present.

에서 수렴하는 FER 값에서도 큰 차이가 존재하였다. 특히 제안한 부호는 매우 큰

에서는 이론적으로 도달 가능한 FER 점에 도달 가능함을 확인할 수 있었다.Referring to FIGS. 7 and 8, in both cases, the proposed code has excellent performance,

There is also a large difference in the FER values converging at In particular, the proposed code is very large

Theoretically reachable FER points can be reached.

The effect of the high code rate protograph-based LDPC code design technique robust to block interference and block fading according to the present invention is as follows.

The conventional technique, which includes a low-code-rate root LDPC code base to make full diversity, utilizes parity more than necessary when the frequency of interference generated in the block interference model is low.

According to at least one of the embodiments of the present invention, a protograph-based LDPC code design method that is close to the optimized performance that can be theoretically obtained when the frequency of interference is low is proposed. To design the proposed code, a base matrix of a specific structure is assumed, and a modified PEXIT algorithm is used to specify a specific value of the base matrix.

The simulation results show that the proposed code has better performance than the regular LDPC code used at the same coding rate.

The foregoing detailed description should not be construed in all aspects as limiting and should be considered illustrative. The scope of the present invention should be determined by rational interpretation of the appended claims, and all changes within the scope of equivalents of the present invention are included in the scope of the present invention.

Claims (4)

Calculating a structure of a basic matrix such that no codeword occurs in one hop;
Calculating an optimized basis matrix through a PEXIT algorithm in which a value of a position corresponding to one hop among channel initial values is modified;
Deriving a parity check matrix through lifting from the calculated basic matrix; And
And designing an LDPC decoder and an encoder that follow the parity check matrix. The high-rate protograph-based LDPC code design scheme is robust against block interference and block fading.
The method according to claim 1,
The size of the base matrix may be,
(L) of the number of hops and a parameter affecting the coding rate. The high-rate protograph-based LDPC code design scheme robust to block interference and block fading.
3. The method of claim 2,
The base matrix includes:
And a sub-matrix corresponding to each hop. The high-rate protograph-based LDPC code design scheme robust to block interference and block fading.
The method according to claim 1,
Wherein the step of calculating the optimized base matrix comprises:
Setting a fading coefficient of a first hop to 0 and a fading coefficient of a hop other than the first hop to a channel value based on a standard deviation of Gaussian noise;
Updating a mutual information value of a variable node and a check node in a protograph relation;
Deriving an accumulated mutual information value of each variable node determined by the channel value; And
The cumulative mutual information value of all the variable nodes becomes 1 to determine whether the decoding of the corresponding protograph structure is successful or the maximum number of iterations during the repeated execution of the steps is reached, And determining whether the decoding of the corresponding protograph structure fails if the value of the protograph-based LDPC code does not reach the maximum value of 1. The high-rate protograph-based LDPC code robust to block interference and block fading Design techniques.

Images