[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR20110000013A - Ldpc code decoding device and ldpc code decoding method - Google Patents

Ldpc code decoding device and ldpc code decoding method Download PDF

Info

Publication number
KR20110000013A
KR20110000013A KR1020090057339A KR20090057339A KR20110000013A KR 20110000013 A KR20110000013 A KR 20110000013A KR 1020090057339 A KR1020090057339 A KR 1020090057339A KR 20090057339 A KR20090057339 A KR 20090057339A KR 20110000013 A KR20110000013 A KR 20110000013A
Authority
KR
South Korea
Prior art keywords
ldpc code
block
decoding
ldpc
deinterleaver
Prior art date
Application number
KR1020090057339A
Other languages
Korean (ko)
Other versions
KR101181969B1 (en
Inventor
김범진
박찬규
Original Assignee
(주)에프씨아이
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by (주)에프씨아이 filed Critical (주)에프씨아이
Priority to KR1020090057339A priority Critical patent/KR101181969B1/en
Priority to CN201010165037.1A priority patent/CN101931497B/en
Publication of KR20110000013A publication Critical patent/KR20110000013A/en
Application granted granted Critical
Publication of KR101181969B1 publication Critical patent/KR101181969B1/en

Links

Images

Classifications

    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105Decoding
    • H03M13/1128Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/27Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
    • H03M13/2778Interleaver using block-wise interleaving, e.g. the interleaving matrix is sub-divided into sub-matrices and the permutation is performed in blocks of sub-matrices
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/3746Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35 with iterative decoding
    • H03M13/3753Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35 with iterative decoding using iteration stopping criteria
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65Purpose and implementation aspects
    • H03M13/6502Reduction of hardware complexity or efficient processing
    • H03M13/6505Memory efficient implementations
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00Arrangements for detecting or preventing errors in the information received
    • H04L1/004Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045Arrangements at the receiver end
    • H04L1/0047Decoding adapted to other signal detection operation
    • H04L1/005Iterative decoding, including iteration between signal detection and decoding operation
    • H04L1/0051Stopping criteria
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00Arrangements for detecting or preventing errors in the information received
    • H04L1/004Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045Arrangements at the receiver end
    • H04L1/0052Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mathematical Physics (AREA)
  • Error Detection And Correction (AREA)

Abstract

PURPOSE: A LDPC code decoding device and a method thereof are provided to reduce a maximum iteration number which is materially required in a single LDPC block by controlling the maximum iteration number of a LDPC code block according to a group unit. CONSTITUTION: A maximum iteration number is calculated from an initial LDPC code block(S400). An i-th LDPC block in a LDPC code group is decoded(S410). The decoding of the LDPC block is completed. An accumulation iteration number is updated when the decoding of the LDPC block is completed(S420). A decoding process is executed to a L-1 block in the LDPC code group(S430). The decoding of a next LDPC code group is executed after the decoding process is completed.

Description

엘디피시 부호의 복호장치 및 방법{LDPC CODE DECODING DEVICE AND LDPC CODE DECODING METHOD}Decoding apparatus and method of LDP code {LDPC CODE DECODING DEVICE AND LDPC CODE DECODING METHOD}

본 발명은 LDPC 부호의 복호장치 및 방법에 관한 것으로, 더욱 상세하게는 반복 복호(Iterative Decoding)방식을 이용하는 복호장치에서 LDPC 부호의 반복(Iteration)수를 제어하는 LDPC 부호의 복호장치 및 방법 관한 것이다.The present invention relates to an apparatus and method for decoding an LDPC code, and more particularly, to an apparatus and method for decoding an LDPC code for controlling the number of iterations of an LDPC code in a decoding apparatus using an iterative decoding method. .

LDPC 부호는 Shannon Limit에 거의 근접하는 성능을 지닌 오류정정부호로 알려져 있으며 DVB/S2, CMMB 등의 이동 방송 통신 분야, 고밀도의 자기기록 장치, 그리고 고속의 광통신 분야 등에 주로 적용되고 있고 그 용도가 점차 확대되는 추세에 있다.LDPC codes are known as error correcting codes that have a performance close to Shannon limit, and are mainly applied to mobile broadcasting communication fields such as DVB / S2 and CMMB, high density magnetic recording devices, and high speed optical communication fields. The trend is expanding.

1996년 이후 LDPC 부호가 ‘재발견’되면서 반복적 복호를 사용하면서도 복잡도가 크게 증가하지 않는 이 부호의 특성 및 생성 방법에 대한 연구가 활기를 띠고 있다. 이러한 LDPC 부호가 `Shannon limit'에 가장 근접하는 오류정정부호로서,터보부호와 더불어 제4세대 이동통신시스템에 활용될 수 있는 매우 우수한 오류 정정부호로 재평가되고 있다.As the LDPC code has been 'rediscovered' since 1996, research on the characteristics and generation method of the code, which uses repetitive decoding but does not increase in complexity, has been vigorous. This LDPC code is an error correcting code closest to the Shannon limit, and is reevaluated as a very good error correcting code that can be used in a fourth generation mobile communication system together with a turbo code.

interleaving의 사전적 의미는 [끼워짜기] 정도로 해석되고, 통신 시스템에서의 의미는 신호를 뒤섞는 방식을 말하며, 전송하려는 데이터의 군집에러를 줄이기 위해 행과 렬의 순서를 바꾸어 보내 줌으로써 공기 중 전달되는 신호가 다중 경로 페이팅 또는 번개나 비등에 의해서 군집에러(Burst Error)가 생길 경우에도 복구 가능한 데이터로 만들어 준다.The dictionary meaning of interleaving is interpreted as "squeeze", and the meaning in a communication system is a method of mixing signals, and a signal transmitted in the air by changing the order of rows and columns to reduce clustering errors of data to be transmitted. It also makes data recoverable even if burst error occurs due to multipath painting or lightning or boiling.

거의 대부분의 LDPC 부호의 복호기는 Sum-Product 알고리즘(Algorithm), Min-Sum 알고리즘 등의 반복복호(Iterative Decoding)방법을 사용하고 있다. 반복 복호방법은 하나의 LDPC 부호 블록을 특정 조건이 만족될 때까지 동일한 과정(이를 Core Process라고 하자)을 반복적으로 여러 번 수행하는 것을 말한다. Almost all LDPC code decoders use iterative decoding methods such as Sum-Product algorithm and Min-Sum algorithm. The iterative decoding method is to repeatedly perform the same process (a core process) several times for one LDPC code block until a specific condition is satisfied.

이때의 특정 조건이란 매 코어 프로세스(Core Process) 수행 후 복호의 결과가 오류 없이 성공적이었는지, 아니면 오류가 아직 포함되어 있는지 확인하는 과정에서의 확인 조건을 말한다(보통 Parity Check이라고 한다). 정정 가능한 오류가 발생한 경우에는 몇 번의 코어 프로세스를 반복하게 되면 오류를 성공적으로 정정하게 되고, 이때에는 이 특정 조건을 만족하게 되어 더 이상 코어 프로세스를 수행하지 않아도 된다. At this time, the specific condition refers to a verification condition in the process of checking whether the decoding result is successful without error after every core process or the error is still included (usually called parity check). If a correctable error occurs, repeating a few core processes successfully corrects the error. At this time, this specific condition is satisfied and the core process no longer needs to be executed.

하지만, 정정할 수 없는 오류가 발생한 경우에는 아무리 코어 프로세스를 반복적으로 수행하더라도 성공적으로 오류를 정정할 수 없다. 그래서, 보통 최대 코어 프로세스의 반복 수행 회수를 제한하는데 이를 최대 반복(Iteration)수라고 한다. 심각한 성능 저하를 방지하기 위해서 적절한 최대 반복 수를 사용해야 하는데 특히 LDPC 부호의 길이가 긴 경우 필요로 하는 최대 반복 수가 30 ~ 50 정도로 상당히 크다. 이렇게, 필요한 최대 반복 수가 증가할수록 LDPC 복호기의 복잡도는 커진다.However, if an uncorrectable error occurs, no matter how repeated the core process is, it cannot be corrected successfully. Thus, it usually limits the number of iterations of the maximum core process, which is called the maximum number of iterations. In order to prevent serious performance degradation, an appropriate maximum number of repetitions should be used, especially when the length of an LDPC code is long, the maximum number of repetitions required is considerably large. Thus, as the maximum number of necessary repetitions increases, the complexity of the LDPC decoder increases.

종래 기술은 개별 LDPC 부호 블록 단위로 최대 반복(Iteration) 수를 독립적으로 제어하는 방법인데 일반적으로 고정된 한 종류의 최대 반복 수를 사용한다. 이런 종래 기술을 적용하면 모든 LDPC 부호 블록 대해 이를 복호할 때 반복 회수를 설정된 최대 값만큼 수행한다고 가정하고 복호기를 설계해야 한다. 이것은 한번의 반복 수행 시에 허용되는 시간을 줄어들게 만들고, 이로 인해 LDPC 복호기에서 보다 많은 병렬 프로세스(Process)들이 필요하게 되어 결국 LDPC 복호기의 복잡도를 증가시키는 문제점이 있다.The prior art is a method of independently controlling the maximum number of iterations in units of individual LDPC code blocks. In general, a fixed type of maximum number of iterations is used. Applying this prior art, the decoder should be designed on the assumption that the number of repetitions is performed as much as the set maximum value when decoding the LDPC code block. This reduces the time allowed in one iteration, which causes more parallel processes in the LDPC decoder, which in turn increases the complexity of the LDPC decoder.

그리고, 인터리버(Interleaver)가 채용된 통신 시스템에서 디인터리버(Deinterleaver)를 구현하는 종래의 기술은 더블 버퍼링(Double Buffering)이 보통이다. 즉 인터리버의 블록 크기의 두 배에 해당되는 메모리를 사용하여 디인터리버를 구현하는 것을 말하는데 하나의 디인터리버 블록(Block)에서는 디인터리버의 입력 데이터에 대한 쓰기 동작을 수행하고 동시에 다른 하나의 블록에서는 씌어진 입력 데이터에 대한 읽기 동작을 수행하여 디인터리버의 출력 데이터로 내 보낸다. 이 방법은 블록 인터리버의 블록 크기의 두 배에 해당하는 메모리를 필요로 하는데 전체 시스템 메모리에서 상당량의 차지할 수도 있는 문제점이 발생한다. In the conventional technology of implementing a deinterleaver in a communication system employing an interleaver, double buffering is common. In other words, the deinterleaver is implemented by using memory that is twice the block size of the interleaver. One deinterleaver block writes the input data of the deinterleaver and another block is written at the same time. Performs a read operation on the input data and exports it to the output data of the deinterleaver. This method requires twice as much memory as the block size of the block interleaver, which can occupy a significant amount of the total system memory.

예를 들면 CMMB라는 중국 이동 방송 시스템에서는 360 x 384 크기의 블록 인터리버를 사용하는데 종래의 기술과 같은 방법으로 디인터리버를 구현하면 총 2x360x384 = 276,480words 만큼의 메모리가 필요하다(1 word = 6bits 인 경우에는 약 1.58Mbits가 필요하다).For example, a Chinese mobile broadcasting system called CMMB uses a 360 x 384 block interleaver. If the deinterleaver is implemented in the same way as in the prior art, a total of 2x360x384 = 276,480 words is required (1 word = 6bits). Requires about 1.58 Mbits).

상기한 종래 문제점을 해결하기 위한 본 발명의 목적은 LDPC 복호기의 복잡도를 줄일 수 있는 장치 및 방법을 제공하는 데 있다.An object of the present invention for solving the above-described problems is to provide an apparatus and method that can reduce the complexity of the LDPC decoder.

그리고, 본 발명의 또 다른 목적은 디인터리버(Deinterleaver) 메모리를 효율적으로 사용하기 위한 장치 및 방법을 제공하는 데 있다..Another object of the present invention is to provide an apparatus and method for efficiently using a deinterleaver memory.

또한, 본 발명의 또 다른 목적은 LDPC 부호와 인터리버를 동시에 채용한 통신시스템에서 동시에 인터리버와 LDPC 부호 그룹 단위의 반복수를 제어하는 장치 및 방법을 제공하는 데 있다.It is still another object of the present invention to provide an apparatus and method for controlling the number of repetitions of an interleaver and an LDPC code group at the same time in a communication system employing an LDPC code and an interleaver at the same time.

상기한 종래 문제점을 해결하고 상기 목적을 달성하기 위한 본 발명은 LDPC 부호장치로부터 부호화된 LDPC(Low Density Parity Check) 부호어 출력을 복호하는 LDPC 부호의 복호장치에 있어서, 상기 LDPC 부호장치에서 전송되는 인터리빙된 LDPC 부호어를 디인터리빙 수행하는 디인터리버와, 상기 디인터리버로부터 출력된 데이터를 입력하여 LDPC 복호를 수행하는 LDPC 복호기로 구성되는 것을 특징으로 한다.The present invention for solving the above problems and to achieve the above object is an LDPC code decoding apparatus for decoding a low density parity check (LDPC) codeword output coded from the LDPC code device, which is transmitted from the LDPC code device And a deinterleaver for deinterleaving the interleaved LDPC codeword, and an LDPC decoder for performing LDPC decoding by inputting data output from the deinterleaver.

본 발명의 LDPC 부호의 복호장치에 있어서, 크기가 M x K(열 수 M, 행 수 K)인 디인터리버(Deinterleaver)를 채용한 복호장치에서 M > K 인 경우에는 M x M으로, 그 반대의 경우에는 K x K인 정방형 메모리를 상기 디인터리버에 사용하는 것 을 특징으로 한다.In the decoding device of the LDPC code of the present invention, the decoding device employing a deinterleaver having a size of M x K (columns M, number of rows K) is M x M when M> K, and vice versa. In the case of K x K, a square memory is used for the deinterleaver.

LDPC 복호장치를 이용한 LDPC 부호의 복호방법에 있어서, 상기 LDPC 부호를 그룹 단위로 반복복호(Iterative Decoding)하여 상기 LDPC 부호 그룹 단위의 최대 반복(Iteration)수를 제어하는 것을 특징으로 한다.A method of decoding an LDPC code using an LDPC decoder, characterized in that the LDPC code is iteratively decoded in group units to control the maximum number of iterations in the LDPC code group unit.

본 발명의 LDPC 부호의 복호방법에 있어서, 크기 L인 상기 LDPC 부호 그룹 내에서 i 번째 부호 블록을 복호할 때 허용된 최대 블록 반복수를 하기 [수학식1]에 의해 결정하는 것을 특징으로 한다.In the decoding method of the LDPC code of the present invention, the maximum number of block repetitions allowed when decoding the i-th code block in the LDPC code group of size L is characterized by the following equation (1).

Figure 112009038790910-PAT00001
Figure 112009038790910-PAT00001

- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i)

- LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG

- LDPC 부호 그룹 내 개별 LDPC 부호 블록의 번호 : i = 0, 1, …, L-1Number of individual LDPC code blocks in an LDPC code group: i = 0, 1,... , L-1

- i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding the i th LDPC code block: ng (i)

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

- NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max

본 발명의 LDPC 부호의 복호방법에 있어서, 상기 [수학식1]은 하기 [수학식2]의 조건을 만족할 때 크기 L인 LDPC 부호 그룹 내에서 i 번째 부호 블록을 복호할 때 허용된 최대 블록 반복수를 하기 [수학식3]에 의해 결정하는 것을 특징으로 한다.In the decoding method of the LDPC code of the present invention, Equation 1 is the maximum block repetition allowed when decoding the i-th code block in the LDPC code group of size L when the condition of Equation 2 is satisfied. The number is characterized by the following [Equation 3].

Figure 112009038790910-PAT00002
Figure 112009038790910-PAT00002

- LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG

- LDPC 부호 그룹 내의 LDPC 부호 블록의 개수 : L-Number of LDPC code blocks in LDPC code group: L

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

Figure 112009038790910-PAT00003
Figure 112009038790910-PAT00003

- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i)

- LDPC 부호 그룹 내 개별 LDPC 부호 블록의 번호 : i = 0, 1, …, L-1Number of individual LDPC code blocks in an LDPC code group: i = 0, 1,... , L-1

- LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding an LDPC code block: ng (i)

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

- NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max

본 발명의 LDPC 부호의 복호방법에 있어서, 상기 디인터리버의 메모리에 대한 읽기와 쓰기는 [규칙1]과 같이 수행하는 것을 특징으로 한다.In the decoding method of the LDPC code of the present invention, reading and writing to the memory of the deinterleaver are performed as shown in [Rule 1].

[규칙1][Rule 1]

M > K 인 경우의 예를 들어, 블록 디인터리버의 동작을 설명하면, 먼저 블록 디인터리버의 입력 데이터를 M개씩 디인터리버 메모리의 열 방향으로 쓰는 것을 K번 반복한다. 한 블록(Block)의 디인터리버 메모리에 쓰기가 끝나면 행 방향으로 K개씩 읽어 나간다. 이때, 읽기와 병행하여 그 다음 디인터리버의 입력 데이터를 행 방향으로 M개씩 쓰기를 진행한다. 이 때 쓰는 위치가 읽어 내는 위치를 추월해서는 안 된다. 그리하여 한 블록의 디인터리버 메모리에 대해 읽기와 쓰기가 끝나면 다시 열 방향에 대해 동일한 방식으로 읽기와 쓰기를 진행한다.For example, in the case of M> K, the operation of the block deinterleaver will be described first by writing M pieces of input data of the block deinterleaver in the column direction of the deinterleaver memory. After writing to a block of deinterleaver memory, K pieces are read in the row direction. At this time, in parallel with reading, M input data of the deinterleaver is written in the row direction. The writing position must not overtake the reading position. Thus, when reading and writing to a block of deinterleaver memory is completed, the reading and writing are performed in the same manner for the column direction again.

본 발명의 LDPC 부호의 복호방법에 있어서, 상기 LDPC 부호 복호방법과, 상기 디인터리버를 채용한 복호장치 및 상기 [규칙1]와 같은 디인터리버를 동시에 채용한 시스템에서 LDPC 부호 그룹의 크기를 하기 [수학식4]와 같이 두는 방법을 특징으로 한다.In the LDPC code decoding method of the present invention, the LDPC code decoding method, the decoding device employing the deinterleaver, and the system employing the deinterleaver as described in [Rule 1] are described below. Equation 4] is characterized in that the method.

Figure 112009038790910-PAT00004
Figure 112009038790910-PAT00004

- LDPC 부호의 길이 : JLDPC code length: J

- 블록 디인터리버의 열 수 : M Number of columns of block deinterleaver: M

- 블록 디인터리버의 행 수 : KNumber of rows of block deinterleaver: K

본 발명의 LDPC 부호의 복호방법에 있어서, 상기 L, M, K, J가 주어진 상태에서 L > ceil(M x K/J) 인 경우에 디인터리버(Deinterleaver)와 LDPC 복호기 사이에 추가적인 버퍼(Buffer) 메모리를 두어 사용하는 것을 특징으로 한다.In the decoding method of the LDPC code of the present invention, an additional buffer between the deinterleaver and the LDPC decoder when L> ceil (M x K / J) when L, M, K, and J are given. A) memory is used.

본 발명의 LDPC 부호의 복호방법에 있어서, 상기 버퍼 메모리의 크기를 하기 [수학식5]와 같은 것을 특징으로 한다.In the decoding method of the LDPC code of the present invention, the size of the buffer memory is as shown in [Equation 5].

Figure 112009038790910-PAT00005
Figure 112009038790910-PAT00005

- LDPC 부호의 길이 : JLDPC code length: J

- ceil (MxK/J) < Lceil (MxK / J) <L

- 블록 디인터리버의 열 수 : M Number of columns of block deinterleaver: M

- 블록 디인터리버의 행 수 : KNumber of rows of block deinterleaver: K

상기한 바와 같이, 본 발명을 적용할 시에는 LDPC 부호 블록들을 그룹 단위로 묶어 그 그룹 단위의 최대 반복수를 제어함으로써 하나의 LDPC 블록에 실질적으로 필요한 최대 반복수를 줄이고, 이로 인해 LDPC 복호기의 복잡도를 줄일 수 있는 효과가 있다.As described above, when the present invention is applied, the LDPC code blocks are grouped into groups to control the maximum number of repetitions of the group, thereby reducing the maximum number of repetitions substantially required for one LDPC block. There is an effect to reduce.

그리고, 본 발명의 LDPC 부호의 복호장치 및 방법은 인터리버(Interleaver)를 채용한 통신시스템에서 디인터리버(Deinterleaver)의 메모리를 효율적으로 사용할 수 있는 장점이 있다.In addition, the apparatus and method for decoding an LDPC code according to the present invention has an advantage that a memory of a deinterleaver can be efficiently used in a communication system employing an interleaver.

또한, 본 발명의 LDPC 부호의 복호장치 및 방법은 인터리버(Interleaver)와 LDPC 부호를 동시에 채용한 통신시스템에서 동시에 인터리버(Interleaver)와 LDPC 그룹 단위로 반복수를 제어하는 효과가 있다.In addition, the apparatus and method for decoding an LDPC code of the present invention has the effect of controlling the number of repetitions in units of an interleaver and an LDPC group simultaneously in a communication system employing an interleaver and an LDPC code.

이하, 첨부된 도면을 참조하여 본 발명에 따른 구체적인 실시 예를 상세하게 설명하면 다음과 같다. Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

도 1은 본 발명에 따른 LDPC 부호의 복호장치를 나타낸 도면이다.1 is a diagram showing a decoding device of an LDPC code according to the present invention.

도 1에 도시한 바와 같이, 본 발명에 따른 LDPC 부호의 복호장치(200)는, LDPC 부호기(110)로부터 LDPC(Low Density Parity Check) 부호를 사용하여 부호화한 후 상기 출력을 인터리버(120)를 통해 인터리빙하여 부호어를 출력하는 LDPC 부호장치(100)와, 상기 LDPC 부호어를 수신하여 디인터리빙을 수행하는 디인터리버(210) 및 상기 디인터리버(210)로부터 출력된 데이터를 입력하여 LDPC 복호를 수행하는 LDPC 복호기(220)로 구성된다.As shown in FIG. 1, the LDPC code decoding apparatus 200 according to the present invention encodes the output of the interleaver 120 after the LDPC coder 110 encodes the low density parity check (LDPC) code. LDPC code device 100 for interleaving and outputting codeword, deinterleaver 210 for receiving the LDPC codeword and performing deinterleaving and data output from the deinterleaver 210 for LDPC decoding. LDPC decoder 220 to perform.

도 2는 일반적인 개별 LDPC 부호 블록에 대한 반복 복호방법을 나타낸 순서도이다.2 is a flowchart illustrating a repetitive decoding method for a typical individual LDPC code block.

도 2에 도시한 바와 같이, 일반적인 개별 LDPC 부호 블록에 대한 반복복호(Iterative Decoding)방법은 다음과 같다.As shown in FIG. 2, an iterative decoding method for a general individual LDPC code block is as follows.

먼저, LDPC 부호의 입력은 일반적으로 LDPC 부호 블록 단위로 Demapper 또는 디인터리버(Deinterleaver)로부터 소프트(Soft) 한 LLR(Log-Likelihood Ratio) 값을 전달 받는다(S200). 이 전달받은 값을 초기값으로 하여 코어 프로세스(Core Process)를 반복적으로(Iterative) 수행하고(S210), 매 반복(Iteration)마다 오류 정정 완료 여부 확인(Parity Check)을 통해 반복을 종료/계속할지를 판정한다(S230). First, the input of the LDPC code generally receives a LLR (Log-Likelihood Ratio) value that is soft from a demapper or a deinterleaver in units of an LDPC code block (S200). The initial value is used as the initial value, and the core process is repeatedly performed (S210), and iterating through the error correction completion check (Parity Check) for each iteration is repeated or not. It is determined (S230).

이때, 만약 미리 설정한 최대 반복수에 도달하면 반복을 종료(S220)하고 오류 정정 결과를 출력(S240)한 다음 복호 과정을 종료한다. At this time, if the preset maximum number of repetitions is reached, the repetition is terminated (S220), an error correction result is output (S240), and the decoding process ends.

도 3a는 종례의 LDPC 복호화 타이밍을 나타낸 도면이고, 도 3b는 본 발명에 따른 LDPC 복호화 타이밍을 나타낸 도면이며, 도 4는 본 발명에 따른 LDPC 부호의 복호방법을 나타낸 순서도이다.3A is a diagram illustrating a conventional LDPC decoding timing, FIG. 3B is a diagram illustrating LDPC decoding timing according to the present invention, and FIG. 4 is a flowchart illustrating a method of decoding an LDPC code according to the present invention.

도 3a에 도시한 바와 같이, 종래의 LDPC 복호화 타이밍(Timing)은 매 LDPC 블록(310)의 복호화 시작 시점이 일정한 간격으로 배치된다. 이 간격 내에는 미리 정해진 최대 블록 반복(Iteration)수(300)에 해당하는 값이 고정된다. As shown in FIG. 3A, in the conventional LDPC decoding timing, the decoding start time points of every LDPC block 310 are arranged at regular intervals. Within this interval, a value corresponding to a predetermined maximum block iteration number 300 is fixed.

그러므로, 한 LDPC 블록의 복호화 과정이 일찍 끝나면 다음 블록의 복호화 시점까지 기다리는 것이 필요하다.Therefore, if the decoding process of one LDPC block ends early, it is necessary to wait until the decoding time of the next block.

도 3b 및 도 4에 도시한 바와 같이, 본 발명의 LDPC 복호화 타이밍에 따른 LDPC 부호의 복호방법은 다음과 같다.As shown in Figs. 3B and 4, the LDPC code decoding method according to the LDPC decoding timing of the present invention is as follows.

먼저, 처음 시작되는 LDPC 부호 블록으로부터 최대 반복수를 계산한다(S400). 그리고, 상기 LDPC 부호 그룹(410)의 i 번째(i = 0, 1, …… L-1) LDPC 블록을 디코딩(Decoding)한다(S410).First, the maximum number of repetitions is calculated from the first LDPC code block (S400). The i-th (i = 0, 1, ..., L-1) LDPC block of the LDPC code group 410 is decoded (S410).

이때, LDPC 블록의 디코딩을 종료한 후 이 때까지의 누적 반복수 ng를 계산하여 갱신 처리한다(S420). At this time, after the decoding of the LDPC block is finished, the cumulative number of repetitions ng up to this point is calculated and updated (S420).

마지막으로, LDPC 부호 그룹(410)의 L-1 번째 블록까지 디코딩을 실행하 며(S430), 디코딩이 완료되면 다음 LDPC 부호 그룹의 디코딩을 수행한다.Finally, decoding is performed up to the L-1th block of the LDPC code group 410 (S430). When decoding is completed, decoding of the next LDPC code group is performed.

이때, 상기 LDPC 부호 그룹의 L-1 번째 블록까지 디코딩이 실행되지 않았으면 다음 LDPC 부호 블록의 복호를 수행하기 위한 최대 반복수를 계산한다(S400).At this time, if decoding is not performed until the L-1th block of the LDPC code group, the maximum number of repetitions for decoding the next LDPC code block is calculated (S400).

여기에서, LDPC 복호화 타이밍은 매 LDPC 블록의 복호화 시작 시점이 일정한 간격으로 배치되지 않고 불규칙적으로 배치된다. 상기 불규칙적인 배치는 한 LDPC 블록의 복호화 과정이 끝나면 지체 없이 다음 LDPC 블록의 복호화 과정을 시작하기 위한 것이다.Here, the LDPC decoding timing is arranged irregularly, rather than at regular intervals, the decoding start time point of every LDPC block. The irregular arrangement is to start the decoding process of the next LDPC block without delay after the decoding process of one LDPC block is completed.

이를 위해서 본 발명은 L 개의 개별 LDPC 부호 블록들을 묶어 이들의 합계 반복(Iteration)수와, 상기 합계 반복수 및 필요한 매개변수(Parameter)를 이용하여, 실시간으로 개별 LDPC 부호 블록에 대한 최대 반복수를 적응적으로 변화시켜가며 제어한다.To this end, the present invention binds L individual LDPC code blocks and calculates the maximum number of repetitions for individual LDPC code blocks in real time by using their total iterations, the total number of iterations, and the necessary parameters. Adaptive change control.

이때, L 개의 LDPC 부호 블록들을 묶어 하나의 LDPC 부호 그룹이라고 하고 LDPC 부호 그룹에 속한 모든 LDPC 부호 블록들의 수를 합하여 이를 그룹 반복수(410)라 한다. 그리고 이와 구별하기 위해 개별 LDPC 부호 블록의 반복수를 블록 반복수(400)라 In this case, L LDPC code blocks are grouped together as one LDPC code group, and the sum of all the LDPC code blocks belonging to the LDPC code group is referred to as a group repetition number 410. In addition, the repetition number of individual LDPC code blocks is referred to as block repetition number 400 to distinguish them.

또한, LDPC 부호 그룹의 최대 그룹 반복수를 NG라고 하고 LDPC 부호 그룹 내에서 i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수를 ng(i)라고 한다.The maximum number of group repetitions of the LDPC code group is called NG, and the cumulative number of group repetitions when the i-th LDPC code block starts to be decoded in the LDPC code group is called ng (i).

상기 개별 LDPC 부호 블록마다 최소로 확보해 주어야 하는 최대 블록 반복수를 NB,min이라고 하고, 이 값의 최대 값을 NB,max라고 하면 i 번째 LDPC 부호 블록 을 복호할 때 허용된 최대 블록 반복수 n(i)는 하기 [수학식1] 같이 주어진다.The maximum number of block repetitions to be secured at least for each individual LDPC code block is NB, min, and if the maximum value of this value is NB, max, the maximum number of block repetitions allowed when decoding the i th LDPC code block (i) is given by Equation 1 below.

만약, LDPC 부호 그룹의 최대 그룹 반복수(NG)를 하기 [수학식2]으로 설정하면 LDPC 부호 그룹 내의 LDPC 부호 블록의 평균 최대 블록 반복수는 NB,min이 되고, 최대 블록 반복수 n(i)는 하기 [수학식3]과 같다.If the maximum group repetition number (NG) of the LDPC code group is set to [Equation 2], the average maximum block repetition number of the LDPC code block in the LDPC code group is NB, min, and the maximum block repetition number n (i ) Is as shown in [Equation 3].

[수학식 1][Equation 1]

Figure 112009038790910-PAT00006
Figure 112009038790910-PAT00006

- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i)

- LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG

- LDPC 부호 그룹 내 개별 LCPC 부호 블록의 번호 : i = 0, 1, …, L-1Number of individual LCPC code blocks in the LDPC code group: i = 0, 1,... , L-1

- i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding the i th LDPC code block: ng (i)

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

- NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max

[수학식 2][Equation 2]

Figure 112009038790910-PAT00007
Figure 112009038790910-PAT00007

- LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG

- LDPC 부호 블록의 개수 : L-Number of LDPC Code Blocks: L

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

[수학식 3]&Quot; (3) &quot;

Figure 112009038790910-PAT00008
Figure 112009038790910-PAT00008

- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i)

- LDPC 부호 그룹 내 개별 LDPC 부호 블록의 번호 : i = 0, 1, … L-1Number of individual LDPC code blocks in an LDPC code group: i = 0, 1,... L-1

- i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding the i th LDPC code block: ng (i)

- 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min

- NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max

상기와 같은 방식은 최소의 최대 블록 반복수 NB,min을 보장해 주면서 그룹 반복수가 여유가 있는 한도 내에서 최대 블록 반복수를 확장해 준다. The above scheme ensures the minimum maximum block repetition number NB, min and expands the maximum block repetition number within the limit of group repetition.

또한, 동일한 평균 최대 반복수를 가진 종래의 기술과 비교할 때 LDPC 복호기 성능을 향상시킨다. 그리고, 동일한 LDPC 복호기 성능을 가진 종래의 기술과 비교할 때 평균 최대 블록 반복수를 줄인다.It also improves LDPC decoder performance compared to the prior art with the same average maximum number of iterations. In addition, the average maximum block repetition number is reduced when compared with the conventional technology having the same LDPC decoder performance.

상기에서 주어진 LDPC 부호와 데이터(Data) 전송속도에 대해 최소로 필요한 최대 블록 반복수 NB,min는 LDPC 복호기의 복잡도를 결정하는 한 요소이다. LDPC 부호의 길이와 부호화율와 데이터 전송속도가 한 블록의 LDCP 부호를 복호 하는데 허용된 최대 복호 시간을 결정한다. The minimum required number of block repetitions, NB, min, for the LDPC code and data transmission rate given above is a factor in determining the complexity of the LDPC decoder. The length, coding rate, and data rate of the LDPC code determine the maximum decoding time allowed for decoding a block of LDCP code.

그리고, 평균 최대 블록 반복수에 의해 한 번의 반복에 허용된 시간이 결정 되며 이것이 코어 프로세스(Core Process)의 복잡도와 메모리 양을 좌우한다. In addition, the time allowed for one iteration is determined by the average maximum number of block iterations, which determines the complexity of the core process and the amount of memory.

여기서, 한 번의 반복에 허용된 시간이 LDPC 복호기의 복잡도를 결정하는 직접적인 중요 요소가 된다. Here, the time allowed for one iteration is a direct factor in determining the complexity of the LDPC decoder.

요약하면 본 발명에서 제시하는 LDPC 부호의 복호기에서 부호 그룹 단위로 반복수를 제어하는 방법은 필요한 평균 최대 블록 반복수를 줄임으로써 한번의 반복에 허용된 시간을 줄일 수 있도록 하여 결국 복호기의 복잡도를 낮출 수 있게 한다.In summary, the method of controlling the repetition number in the code group unit in the decoder of the LDPC code proposed in the present invention can reduce the complexity of the decoder by reducing the time allowed for one repetition by reducing the required maximum number of block repetitions. To be able.

이하, 일반적인 통신시스템에서 LDPC 부호와 같은 채널 부호는 연집오류(Burst Error)에 대한 영향을 줄이기 위해 인터리버(Interleaver)와 연결하여 사용된다. 인터리버에는 크게 블록 인터리버(Block Interleaver)와 회선 인터리버(Convolutional Interleaver)가 있는데 본 발명에서는 LDPC 부호를 블록 인터리버와 연결하여 사용하는 시스템에, 앞서 언급한 LDPC 부호 그룹 단위로 복호기의 반복수를 제어하는 방법에 대해 제시한다.Hereinafter, in a general communication system, a channel code such as an LDPC code is used in connection with an interleaver in order to reduce an influence on burst error. The interleaver includes a block interleaver and a convolutional interleaver. In the present invention, a method for controlling the number of iterations of a decoder in units of the aforementioned LDPC code groups in a system using an LDPC code connected to a block interleaver. To present.

도 5a는 종례의 블록 인터리버의 구성을 나타낸 도면이고, 도 5b는 본 발명에 따른 블록 디인터리버의 구성을 나타낸 도면이다.5A is a diagram showing the configuration of a conventional block interleaver, and FIG. 5B is a diagram showing the configuration of a block deinterleaver according to the present invention.

도 5a에 도시한 바와 같이, 종례의 인터리버는 상기 블록 인터리버(500)의 크기를 M x K (열 수 M, 행 수 K)라고 하면 종래 기술은 두 개의 디인터리버링(Deinterleaving) 블록으로 구성된 메모리를 이용한 더블 버퍼링(Double Buffering) 방법으로서 하나의 블록에서는 디인터리버(Deinterleaver)의 입력 데이터에 대한 쓰기 동작을, 다른 하나의 블록에서는 이미 쓰여진 입력 데이터에 대한 읽기 동작을 수행하여 이를 디인터리버 출력으로 내보낸다.As shown in FIG. 5A, a conventional interleaver may have a size of the block interleaver 500 as M × K (columns M, rows K), and the conventional technology may include two deinterleaving blocks. Double Buffering using Double Buffering method. In one block, write operation is performed on the input data of the deinterleaver, and in another block, the read operation is performed on the already written input data. send.

도 5b에 도시한 바와 같이, 본 발명에 따른 블록 디인터리버(600)는 (M x K)와 LDPC 부호의 길이 J와의 관계(ceil (M x K/J) = L 또는 floor (M x K/J) = L, 이 때 L은 복호기에서 관리하는 LDPC 부호 그룹의 크기임)를 이용하여 M > K 인 경우에는 디인터리버(Deinterleaver)의 메모리를 M x M으로, 그 반대의 경우에는 K x K로 구성하여 더블 버퍼링 없이 하나의 디인터리버 메모리 블록(600a, 600b)으로 디인터리버를 구현한다.As shown in FIG. 5B, the block deinterleaver 600 according to the present invention has a relationship between (M x K) and the length J of the LDPC code (ceil (M x K / J) = L or floor (M x K / J) = L, where L is the size of the LDPC code group managed by the decoder), where M> K, the memory of the deinterleaver is M x M, and vice versa. The deinterleaver is implemented as one deinterleaver memory block 600a or 600b without double buffering.

여기서, M > K 인 경우의 예를 들어 디인터리버 동작을 설명하면, 먼저 디인터리버 블록의 입력 데이터를 M개씩 디인터리버 메모리의 열(Row) 방향으로 쓰는 것을 K번 반복한다. 한 블록의 디인터리버 메모리에 쓰기가 끝나면 행(Column) 방향으로 K개씩 읽어 나간다. 이 때 읽기와 병행하여 그 다음 디인터리버의 입력 데이터를 행 방향으로 M개씩 쓰기를 진행한다. 이 때 쓰는 위치가 읽어 내는 위치를 추월해서는 안 된다. 그리하여 한 블록의 디인터리버 메모리에 대해 읽기와 쓰기가 끝나면 다시 열 방향에 대해 동일한 방식으로 읽기와 쓰기를 진행한다[규칙1].Here, a description will be given of the deinterleaver operation in the case of M> K. First, the input data of the deinterleaver block is repeated M times in the row direction of the deinterleaver memory. After writing to a block of deinterleaver memory, K data are read in the column direction. At this time, in parallel with reading, M input data of the deinterleaver is written in the row direction. The writing position must not overtake the reading position. Thus, when reading and writing to a block of deinterleaver memory is completed, read and write are performed in the same manner in the column direction again [Rule 1].

이와 같은 상기 [규칙1]은 하나의 인터리버 블록보다 조금 더 큰 정방형의 메모리 블록만을 이용하여 디인터리버링(Deinterleaving)에 필요한 쓰기와 읽기를 동시에 수행한다. [Rule 1] performs write and read at the same time necessary for deinterleaving using only square memory blocks that are slightly larger than one interleaver block.

또한, LDPC 부호 그룹의 크기 L을 필요에 따라 하기 [수학식4]로 두면 상기 언급한 방식으로 LDPC 복호기의 그룹 반복수를 제어한다.Also, if the size L of the LDPC code group is set as Equation 4 below, the number of group repetitions of the LDPC decoder is controlled in the above-described manner.

[수학식 4]&Quot; (4) &quot;

Figure 112009038790910-PAT00009
Figure 112009038790910-PAT00009

- LDPC 부호의 길이 : JLDPC code length: J

- 블록 디인터리버의 열 수 : M Number of columns of block deinterleaver: M

- 블록 디인터리버의 행 수 : KNumber of rows of block deinterleaver: K

이때, 종례 CMMB의 경우를 예로 들면 M = 360, K = 384 인데 종래의 기술인 더블 버퍼링(Double Buffering)방법에서는 총 2 x 360 x 384 = 276,480words의 메모리가 필요한데 반하여 본 발명에서 제시하는 방법에서는 384 x 384 = 147,456words의 메모리 만이 필요하다. 이것은 더블 버퍼링 구성(Double Buffering Scheme)의 약 53.3%에 지나지 않는 양이다.In this case, for example, the case of the case CMMB is M = 360, K = 384, while the conventional double buffering method requires a total of 2 x 360 x 384 = 276,480 words of memory, whereas the method proposed in the present invention is 384. x 384 = Only 147,456 words of memory are needed. This is only about 53.3% of the Double Buffering Scheme.

본 발명에서 제시하는 방법에서는 주어진 평균 최대 블록 반복수에 대해 필요한 성능을 만족시키기 위해서 L을 충분히 크게 해야 한다. 이 때 L 값이 인터리버의 크기(더 정확하게는 ceil (M x K/J))보다 큰 경우에는 디인터리버와 LDPC 복호기 사이에 추가적인 버퍼(Buffer) 메모리를 두어 구현한다. In the method proposed in the present invention, L must be made large enough to satisfy the required performance for a given average maximum block repetition number. In this case, if the L value is larger than the size of the interleaver (more precisely ceil (M x K / J)), an additional buffer memory is provided between the deinterleaver and the LDPC decoder.

예를 들면, 하기 [수학식5] 크기만큼의 버퍼(Buffer)를 두어 쉽게 구현한다.For example, it is easy to implement a buffer as large as [Equation 5] below.

[수학식 5][Equation 5]

Figure 112009038790910-PAT00010
Figure 112009038790910-PAT00010

- LDPC 부호의 길이 : JLDPC code length: J

- ceil (MxK/J) < Lceil (MxK / J) <L

- 블록 디인터리버의 열 수 : M Number of columns of block deinterleaver: M

- 블록 디인터리버의 행 수 : KNumber of rows of block deinterleaver: K

이상에서 설명한 바와 같이, 본 발명의 상세한 설명에서는 본 발명의 바람직한 실시 예에 관하여 설명하였으나, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면 본 발명의 범주에서 벗어나지 않는 한도 내에서 여러 가지 변형이 가능함은 물론이다. 따라서 본 발명의 권리 범위는 설명된 실시 예에 국한되어 정해져서는 안되며, 후술하는 청구범위뿐만 아니라, 이와 균등한 것들에 의해 정해져야 한다.While the present invention has been particularly shown and described with reference to exemplary embodiments, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, Of course, this is possible. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be defined by the equivalents as well as the claims to be described later.

도 1은 본 발명에 따른 LDPC 부호의 복호장치를 나타낸 도면이다.1 is a diagram showing a decoding device of an LDPC code according to the present invention.

도 2는 일반적인 개별 LDPC 부호 블록에 대한 반복복호방법을 나타낸 순서도이다.2 is a flowchart illustrating a repetitive decoding method for a typical individual LDPC code block.

도 3a는 종례의 LDPC 복호화 타이밍을 나타낸 도면이다. 3A is a diagram illustrating a conventional LDPC decoding timing.

도 3b는 본 발명에 따른 LDPC 복호화 타이밍을 나타낸 도면이다. 3B illustrates LDPC decoding timing according to the present invention.

도 4는 본 발명에 따른 LDPC 부호의 복호방법을 나타낸 순서도이다.4 is a flowchart illustrating a decoding method of an LDPC code according to the present invention.

도 5a는 종례의 인터리버의 구성을 나타낸 도면이다. 5A is a diagram illustrating a configuration of a conventional interleaver.

도 5b는 본 발명에 따른 인터리버의 구성을 나타낸 도면이다.5B is a diagram showing the configuration of an interleaver according to the present invention.

*** 도면의 주요 부분에 대한 설명 ****** Description of the main parts of the drawing ***

100 : LDPC 부호 장치 110 : LDPC 부호기100: LDPC encoder 110: LDPC encoder

120 : 인터리버 200 : LDPC 복호 장치120: interleaver 200: LDPC decoding device

210 : 디인터리버 220 : LDPC 복호기210: deinterleaver 220: LDPC decoder

300 : LDPC 부호 블록의 고정 반복수 310 : LDPC 부호 블록300: fixed repetition number of LDPC code block 310: LDPC code block

400 : LDPC 부호 블록의 가변 반복수 410 : LDPC 부호 그룹400: variable repetition number of LDPC code block 410: LDPC code group

500 : 블록 인터리버 600 : 블록 디인터리버500: block interleaver 600: block deinterleaver

Claims (9)

LDPC 부호장치로부터 부호화된 LDPC(Low Density Parity Check) 부호어 출력을 복호하는 LDPC 부호의 복호장치에 있어서, In the LDPC code decoding device for decoding the LDPC coded low-density parity check codeword output from the LDPC coder, 상기 LDPC 부호장치에서 전송되는 인터리빙된 LDPC 부호어를 디인터리빙 수행하는 디인터리버와;A deinterleaver for deinterleaving the interleaved LDPC codeword transmitted from the LDPC coder; 상기 디인터리버로부터 출력된 데이터를 입력하여 LDPC 복호를 수행하는 LDPC 복호기;로 구성되는 것을 특징으로 하는 LDPC 복호장치.LDPC decoder for performing LDPC decoding by inputting the data output from the deinterleaver. 제 1항에 있어서,The method of claim 1, 크기가 M x K(열 수 M, 행 수 K)인 디인터리버(Deinterleaver)를 채용한 복호장치에서 M > K 인 경우에는 M x M으로, 그 반대의 경우에는 K x K인 정방형 메모리를 상기 디인터리버에 사용하는 것을 특징으로 하는 LDPC 부호의 복호장치.In a decoding apparatus employing a deinterleaver of size M x K (columns M, rows K), a square memory of M x M for M> K and vice versa is described. LDPC code decoding device, characterized in that used for the deinterleaver. 엘디피시(LDPC) 복호장치를 이용한 엘디피시 부호의 복호방법에 있어서,In the decoding method of the LDP code using the LDPC decoding device, 상기 LDPC 부호를 그룹 단위로 반복복호(Iterative Decoding)하여 상기 LDPC 부호 그룹 단위의 최대 반복(Iteration)수를 제어하는 것을 특징으로 하는 LDPC 부호의 복호방법.And decoding the LDPC code in group units to control the maximum number of iterations in the LDPC code group unit. 제 3항에 있어서,The method of claim 3, wherein 크기 L인 상기 LDPC 부호 그룹 내에서 i 번째 부호 블록을 복호할 때 허용된 최대 블록 반복수를 하기 [수학식1]에 의해 결정하는 것을 특징으로 하는 LDPC 부호의 복호방법.The decoding method of the LDPC code, characterized in that the maximum number of block iterations allowed when decoding the i-th code block in the LDPC code group of size L is determined by the following equation (1). [수학식 1][Equation 1]
Figure 112009038790910-PAT00011
Figure 112009038790910-PAT00011
- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i) - LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG - LDPC 부호 그룹 내 개별 LCPC 부호 블록의 번호 : i = 0, 1, …, L-1Number of individual LCPC code blocks in the LDPC code group: i = 0, 1,... , L-1 - i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding the i th LDPC code block: ng (i) - 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min - NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max
제 4항에 있어서,The method of claim 4, wherein 상기 [수학식1]은 하기 [수학식2]의 조건을 만족할 때 크기 L인 LDPC 부호 그룹 내에서 i 번째 부호 블록을 복호할 때 허용된 최대 블록 반복수를 하기 [수학식3]에 의해 결정하는 것을 특징으로 하는 LDPC 부호의 복호방법.[Equation 1] is determined by Equation 3 to determine the maximum number of block repetitions allowed when decoding the i-th code block in the LDPC code group of size L when the condition of Equation 2 is satisfied. LDPC code decoding method characterized in that. [수학식 2][Equation 2]
Figure 112009038790910-PAT00012
Figure 112009038790910-PAT00012
- LDPC 부호 그룹의 최대 그룹 반복수 : NGMaximum number of group repetitions of an LDPC code group: NG - LDPC 부호 그룹 내 LDPC 부호 블록의 개수 : L-Number of LDPC code blocks in LDPC code group: L - 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min [수학식 3]&Quot; (3) &quot;
Figure 112009038790910-PAT00013
Figure 112009038790910-PAT00013
- i 번째 LCPC 부호 블록에 허용된 최대 반복수 : n(i)The maximum number of iterations allowed for the i th LCPC code block: n (i) - LDPC 부호 그룹 내 개별 LDPC 부호 블록의 번호 : i = 0, 1, …, L-1Number of individual LDPC code blocks in an LDPC code group: i = 0, 1,... , L-1 - i 번째 LDPC 부호 블록을 복호하기 시작할 때의 누적 그룹 반복수 : ng(i)Cumulative number of group iterations at the start of decoding the i th LDPC code block: ng (i) - 개별 LDPC 부호 블록마다 최소로 확보해야 하는 최대 블록 반복수 : NB,min-Maximum number of block repetitions to be secured minimum for each LDPC code block: NB, min - NB,min값의 최대 값 : NB,max-Maximum value of NB, min: NB, max
제 2항에 있어서,3. The method of claim 2, 상기 디인터리버의 메모리에 대한 읽기와 쓰기는 [규칙1]과 같이 수행하는 것을 특징으로 하는 LDPC 부호의 복호방법.The decoding and decoding of the LDPC code, characterized in that the reading and writing of the memory of the deinterleaver are performed as shown in [Rule 1]. [규칙1][Rule 1] M > K 인 경우의 예를 들어, 블록 디인터리버의 동작을 설명하면, 먼저 블록 디인터리버의 입력 데이터를 M개씩 디인터리버 메모리의 열 방향으로 쓰는 것을 K번 반복한다. 한 블록(Block)의 디인터리버 메모리에 쓰기가 끝나면 행 방향으로 K개씩 읽어 나간다. 이때 읽기와 병행하여 그 다음 디인터리버의 입력 데이터를 행 방향으로 M개씩 쓰기를 진행한다. 이때 쓰는 위치가 읽어내는 위치를 추월해서는 안 된다. 그리하여 한 블록의 디인터리버 메모리에 대해 읽기와 쓰기가 끝나면 다시 열 방향에 대해 동일한 방식으로 읽기와 쓰기를 진행한다.For example, in the case of M> K, the operation of the block deinterleaver will be described first by writing M pieces of input data of the block deinterleaver in the column direction of the deinterleaver memory. After writing to a block of deinterleaver memory, K pieces are read in the row direction. At this time, in parallel with reading, M input data of the deinterleaver is written in the row direction. The writing position must not overtake the reading position. Thus, when reading and writing to a block of deinterleaver memory is completed, the reading and writing are performed in the same manner for the column direction again. 제 1항, 2항, 3항, 6항 중 어느 한 항에 있어서,The method according to any one of claims 1, 2, 3, 6, 상기 LDPC 부호 복호방법과, 상기 디인터리버를 채용한 복호장치 및 상기 [규칙1]와 같은 디인터리버를 동시에 채용한 시스템에서 LDPC 부호 그룹의 크기를 하기 [수학식4]와 같이 두는 방법을 특징으로 하는 LDPC 부호의 복호방법.In the LDPC code decoding method, the decoding device employing the deinterleaver and the system employing the deinterleaver as shown in [Rule 1], the size of the LDPC code group is expressed as [Equation 4] below. LDPC code decoding method. [수학식 4]&Quot; (4) &quot;
Figure 112009038790910-PAT00014
Figure 112009038790910-PAT00014
- LDPC 부호의 길이 : JLDPC code length: J - 블록 디인터리버의 열 수 : M Number of columns of block deinterleaver: M - 블록 디인터리버의 행 수 : KNumber of rows of block deinterleaver: K
제 7항에 있어서,The method of claim 7, wherein 상기 L, M, K, J가 주어진 상태에서 L > ceil(MxK/J) 인 경우에 디인터리버(Deinterleaver)와 LDPC 해독기 사이에 추가적인 버퍼(Buffer) 메모리를 두어 사용하는 것을 특징으로 하는 LDPC 부호의 복호방법.In the state where L, M, K, and J, L> ceil (MxK / J), an additional buffer memory is provided between the deinterleaver and the LDPC decoder. Decryption method. 제 8항에 있어서,The method of claim 8, 상기 버퍼 메모리의 크기를 하기 [수학식5]와 같은 것을 특징으로 하는 LDPC 부호의 복호방법.And a size of the buffer memory as shown in [Equation 5]. [수학식 5][Equation 5]
Figure 112009038790910-PAT00015
Figure 112009038790910-PAT00015
- LDPC 부호의 길이 : JLDPC code length: J - ceil (M x K/J) < Lceil (M x K / J) <L - 열 수 : M Number of columns: M - 행 수 : KNumber of rows: K
KR1020090057339A 2009-06-26 2009-06-26 Ldpc code decoding method KR101181969B1 (en)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020090057339A KR101181969B1 (en) 2009-06-26 2009-06-26 Ldpc code decoding method
CN201010165037.1A CN101931497B (en) 2009-06-26 2010-04-12 Decoding device and method for low-density parity-check (LDPC)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020090057339A KR101181969B1 (en) 2009-06-26 2009-06-26 Ldpc code decoding method

Publications (2)

Publication Number Publication Date
KR20110000013A true KR20110000013A (en) 2011-01-03
KR101181969B1 KR101181969B1 (en) 2012-09-11

Family

ID=43370442

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020090057339A KR101181969B1 (en) 2009-06-26 2009-06-26 Ldpc code decoding method

Country Status (2)

Country Link
KR (1) KR101181969B1 (en)
CN (1) CN101931497B (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012096455A2 (en) 2011-01-10 2012-07-19 Lee Dong-Won Led lighting device including a highly-efficient power supply
US8826096B2 (en) 2011-12-29 2014-09-02 Korea Advanced Institute Of Science And Technology Method of decoding LDPC code for producing several different decoders using parity-check matrix of LDPC code and LDPC code system including the same

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9266182B2 (en) 2012-04-06 2016-02-23 Illinois Tools Works Inc. Welding torch with a temperature measurement device
US9415459B2 (en) 2012-04-06 2016-08-16 Illinois Tool Works Inc. Welding systems having non-contact temperature measurement systems
TWI530959B (en) * 2014-06-17 2016-04-21 慧榮科技股份有限公司 Method for controlling a memory apparatus, and associated memory apparatus thereof and associated controller thereof
CN111355494B (en) * 2018-12-24 2024-09-20 中兴通讯股份有限公司 Verification code processing method and device and electronic equipment

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4097852B2 (en) * 1999-08-26 2008-06-11 株式会社フィリップスエレクトロニクスジャパン Data writing / reading method, deinterleaving method, data processing method, memory, and memory driving device
KR100413421B1 (en) * 1999-10-08 2003-12-31 엘지전자 주식회사 Method for dual Interleaving
CN100566182C (en) * 2005-02-26 2009-12-02 美国博通公司 The accelerated message passing decoder of adapted for decoding LDPC code signal and method
CN101150377A (en) * 2006-09-18 2008-03-26 国家广播电影电视总局广播科学研究院 Bit mapping scheme of 32APSK system for low-density checksum coding
CN100542049C (en) * 2007-03-23 2009-09-16 北京航空航天大学 A kind of decoder device and interpretation method of LDPC sign indicating number of multi code Rate of Chinese character

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012096455A2 (en) 2011-01-10 2012-07-19 Lee Dong-Won Led lighting device including a highly-efficient power supply
US8826096B2 (en) 2011-12-29 2014-09-02 Korea Advanced Institute Of Science And Technology Method of decoding LDPC code for producing several different decoders using parity-check matrix of LDPC code and LDPC code system including the same

Also Published As

Publication number Publication date
KR101181969B1 (en) 2012-09-11
CN101931497B (en) 2014-12-17
CN101931497A (en) 2010-12-29

Similar Documents

Publication Publication Date Title
US9459956B2 (en) Data decoder with trapping set flip bit mapper
US8929009B2 (en) Irregular low density parity check decoder with low syndrome error handling
US7853854B2 (en) Iterative decoding of a frame of data encoded using a block coding algorithm
US8918696B2 (en) Implementation of LDPC selective decoding scheduling
KR101181969B1 (en) Ldpc code decoding method
US20140053037A1 (en) Multi-Level LDPC Layered Decoder With Out-Of-Order Processing
US8583979B1 (en) Multiple interleavers in a coding system
EP2741421A1 (en) Low density parity check decoder with miscorrection handling
US8321746B2 (en) Systems and methods for quasi-cyclic LDPC code production and decoding
US8880976B2 (en) Method and apparatus for encoding LBA information into the parity of a LDPC system
EP2780808A2 (en) Data encoder and decoder using memory-specific parity-check matrix
US8566665B2 (en) Systems and methods for error correction using low density parity check codes using multiple layer check equations
US9214959B2 (en) Systems and methods for skip layer data decoding
US8196002B2 (en) Systems and methods for joint LDPC encoding and decoding
US11522562B2 (en) Error correcting decoding device and error correcting decoding method
KR101657912B1 (en) Method of Decoding Non-Binary Low Density Parity Check Codes
CN101847447A (en) Memory controller, storage controlling method and data access arrangement
US8949696B2 (en) Systems and methods for trapping set disruption
EP2665190B1 (en) Decoding of non-binary codes with symbol re-grouping
US8443250B2 (en) Systems and methods for error correction using irregular low density parity check codes
US8650456B2 (en) Decoder based data recovery
CN113131947B (en) Decoding method, decoder and decoding device
KR101484066B1 (en) Ldpc code decoding method
JP7038910B2 (en) Decoding device, control circuit and storage medium
US8775898B2 (en) Systems and methods for hardware flexible low density parity check conversion

Legal Events

Date Code Title Description
A201 Request for examination
E902 Notification of reason for refusal
E902 Notification of reason for refusal
E701 Decision to grant or registration of patent right
GRNT Written decision to grant
FPAY Annual fee payment

Payment date: 20150903

Year of fee payment: 4

FPAY Annual fee payment

Payment date: 20160905

Year of fee payment: 5

FPAY Annual fee payment

Payment date: 20170905

Year of fee payment: 6

FPAY Annual fee payment

Payment date: 20180903

Year of fee payment: 7

FPAY Annual fee payment

Payment date: 20190902

Year of fee payment: 8