KR100491338B1

KR100491338B1 - Method for decoding error correction codes using approximate function

Info

Publication number: KR100491338B1
Application number: KR10-2002-0034987A
Authority: KR
Inventors: 명세호; 양경철; 오민석
Original assignee: 엘지전자 주식회사; 학교법인 포항공과대학교
Priority date: 2002-06-21
Filing date: 2002-06-21
Publication date: 2005-05-27
Anticipated expiration: 2022-06-21
Also published as: KR20040000060A

Abstract

본 발명은 디지털 데이터 수신 장치에 있어서, 특히 오류정정부호의 복호를 위해 근사화 함수가 복호 과정에서 사용될 때 복호 연산을 간략화 될 수 있도록 한 근사화 함수를 사용하는 오류정정부호의 복호 방법에 관한 것이다.The present invention relates to a method of decoding an error correcting code using an approximation function that can simplify a decoding operation when an approximation function is used in a decoding process, in particular for decoding an error correcting code.

본 발명에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법은, 디지털 데이터 수신 장치에 있어서, 음수 값을 갖지 않고 함수축에 대칭인 함수를 선택하는 단계; 변수 구간을 적어도 3개의 구간으로 나누어 각 구간별로 상기 함수에 근사 하는 선형 함수를 선택하는 단계; 입력되는 두개의 메시지의 값을 연산하여 구한 두개의 값이 상기 변수 구간 가운데 어디에 속하는지 구분하는 단계; 상기 구간에 대응하는 상기 선형 함수를 연산하여 두개의 함수값을 구하는 단계; 상기 두개의 함수값의 차를 출력하는 단계를 포함하여 이루어지는 것을 특징으로 한다.According to an aspect of the present invention, there is provided a method of decoding an error correcting code using an approximation function, comprising: selecting a function symmetrical to a function axis without having a negative value; Dividing the variable interval into at least three intervals and selecting a linear function approximating the function for each interval; Calculating where two values obtained by calculating values of two input messages belong to one of the variable periods; Calculating two function values by calculating the linear function corresponding to the interval; And outputting the difference between the two function values.

Description

Method for decoding error correction codes using approximate function}

본 발명은 디지털 데이터 수신 장치에의 오류 정정 부호(error-correcitng codes)의 복호에 관한 것으로, 근사화 함수[ln(cosh(x))]가 복호 과정에서 사용될 때, 복호 연산을 단순하게 할 수 있는 근사식으로 근사화시켜 복호화할 수 있도록 한 근사화 함수를 사용하는 오류정정부호의 복호 방법에 관한 것이다. The present invention relates to the decoding of error-correcitng codes to a digital data receiving apparatus. When the approximation function [ln (cosh (x))] is used in the decoding process, the decoding operation can be simplified. The present invention relates to a decoding method of an error correcting code using an approximation function that can be approximated and decoded.

LDPC(Low Density Parity Check) 부호와 RA(Repeat Accumulate) 부호 등의 복호에 사용되는 팩터 그래프는 다 변수의 전체 함수(global function)가 어떻게 국소 함수(local function)들의 곱으로 인수분해 되는지를 표현한 두 갈래의 그래프(bipartite graph)로서, 패리트 검사를 위한 검사노드(check node)와 정보어 심볼 혹은 부호어 심볼을 나타내는 변수 노드(variable node)로 구성되어 있다. 이러한 팩터 그래프 상에서 요약 연산이나 주변 연산을 수행하는데, 적용되는 합곱(sum-product) 알고리즘은 이러한 두 노드들에 대해 각각 메시지 전달에 관한 갱신 규칙이 있다. 상기 LDPC부호는 터보 부호 보다 우수한 성능, 낮은 복호 복잡도, 병렬 처리로 고속 처리가 가능하기 때문에 4세대 이동통신 시스템에 적합한 구조를 가지고 있다.Factor graphs used for decoding Low Density Parity Check (LDPC) codes and Repeat Accumulate (RA) codes are two representations of how the global function of a multivariate is factored into the product of local functions. Bipartite graph, consisting of a check node for parit check and a variable node representing an information word symbol or a code word symbol. Perform summarization or marginal operations on these factor graphs, and the sum-product algorithm applied has update rules for message delivery for each of these two nodes. The LDPC code has a structure suitable for a fourth generation mobile communication system because the LDPC code has higher performance, lower decoding complexity, and high-speed processing in parallel processing.

특히 이진 부호의 경우 팩터 그래프 이론과 합곱 알고리즘에 기초하여 복호를 할 때, 메시지들을 로그 라이클리후드 비율(Log Likelihood Ratio, LLR)로 가정하면, 변수 노드에서는 단순한 합 연산으로, 패리티 검사를 하는 검사 노드에서는 근사화 함수 tanh(x) 또는 ln(cosh(x))를 이용한 메시지 전달 규칙이 적용된다.Especially for binary codes, when decoding based on factor graph theory and sum product algorithm, assuming that messages are Log Likelihood Ratio (LLR), parity check is performed by simple sum operation at variable node. The node applies the message passing rule using the approximation function tanh (x) or ln (cosh (x)).

예를 들어, 검사 노드에 들어오는 두 개의 입력 메시지( ) 에 대한 출력은 다음과 같은 식 1로 갱신된다.For example, two input messages coming into a probe node ( The output for) is updated to the following equation.

여기서, 여러 개의 입력이 들어올 경우에는 위와 같은 식을 재귀적(recursive)으로 사용한다.Here, when multiple inputs come in, the above expression is used recursively.

이러한 tanh(x) 또는 in(cosh(x))를 이용한 복호 방법은 함수의 특성상 이들 두 함수를 그대로 적용할 경우 상당히 복잡한 연산 문제를 야기한다. 따라서 실제로 적용되는 알고리즘은 tanh(x) 또는 in(cosh(x))의 값들을 룩업 표(Look-up table)를 이용하여 저장한 다음 연산 과정 중 필요한 값들을 불러내어 사용하게 된다.The decoding method using tanh (x) or in (cosh (x)) causes a complicated computational problem if these two functions are applied as they are. Therefore, the algorithm that is actually applied stores the values of tanh (x) or in (cosh (x)) using a look-up table and then retrieves and uses the necessary values during the calculation process.

이에 대해 룩업 표를 사용하지 않고 필요한 메모리를 감소시키는 방법으로 최소합(min-sum) 알고리즘이 있다. 이 알고리즘은 in(cosh(x)) 함수가 의 범위에서 에 수렴하는 성질을 이용하여 수학식 2와 같은 방법을 이용한다.There is a min-sum algorithm to reduce the required memory without using a lookup table. This algorithm uses the in (cosh (x)) function In the range of Using a property that converges to the same method as in Equation 2.

이러한 최소합 알고리즘은 단순한 비교 연산과 메시지 부호(sign)만을 검사하는 연산만이 필요하므로, 연산을 위해 룩업 표가 필요 없고 또 매우 빠른 연산을 수행할 수 있다.This minimum sum algorithm requires only a simple comparison operation and an operation that checks only the message sign, so that a lookup table is not required for the operation and a very fast operation can be performed.

그러나, 근사식을 사용하지 않는 복호 방법에서는 좀 더 정밀한 근사화 함수 tanh(x) 또는 ln(cosh(x)) 값이 요구될수록 룩업 표의 크기는 증가하게 되어, 필요한 메모리의 수가 많아진다. 또한 임의의 수들에 대한 곱셈 연산이 있으므로 연산이 복잡해 지며, 시간 지연도 더 길어지게 된다.However, in a decoding method that does not use an approximation equation, the more precise the approximation function tanh (x) or ln (cosh (x)) value is required, the larger the size of the lookup table becomes and the more memory is required. There is also a multiplication operation for arbitrary numbers, which complicates the operation and results in longer time delays.

이에 대해 근사식을 이용한 복호 방법인 최소합 알고리즘을 사용함으로써, 연산을 단순화하여 매우 빠르고 룩업 표가 필요 없는 방법이 제안되어 있으나, 이는 커다란 성능의 열화를 가져온다.By using a minimum sum algorithm, which is a decoding method using an approximation formula, a method is proposed which simplifies the operation and does not need a lookup table. However, this results in a large performance deterioration.

본 발명은 근사화 함수에 상수값 또는 일차 선형 함수, 양자화를 통하여 구한 근사식을 복호에 적용함으로써, 성능의 열화는 최소화하면서 연산을 단순화하고 또한 룩업 표가 필요없는 근사화 함수의 근사화 방법을 제공함에 그 목적이 있다.The present invention provides a method of approximating an approximation function by applying a constant value, a linear linear function, or an approximation equation obtained through quantization to the approximation function, simplifying the operation while minimizing performance degradation, and not requiring a lookup table. There is a purpose.

다른 목적은 근사화 함수가 음의 값을 갖지 않고 원점을 지나며, y축에 대칭은 구조를 갖는 함수이므로, 상기 근사화 함수에서 변수의 절대값 크기가 어느 정도 커지게 되면 로 적용하는 한편, 변수의 절대값이 작은 부분에 대한 근사식의 적용에 따라 복호 성능의 열화를 가져오는 것을 방지하도록, 변수의 절대값이 작은 부분에 대한 함수 값을 선형 함수나 함수의 양자화를 통해서 근사화하여 사용함으로써, 성능을 개선할 수 있도록 한 근사화 함수의 근사화 방법을 제공함에 그 목적이 있다.Another objective is that the approximation function has no negative value and passes through the origin, and that the symmetry on the y-axis is a function. On the other hand, the function value for the small absolute value of the variable is converted into a linear function or a function quantization to prevent deterioration of decoding performance by applying an approximation to the small absolute value of the variable. The purpose of the present invention is to provide an approximation method of the approximation function that can improve the performance by using approximation.

상기한 목적 달성을 위한 본 발명에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법은, Decoding method of an error correcting code using an approximation function according to the present invention for achieving the above object,

디지털 데이터 수신 장치에 있어서,In the digital data receiving apparatus,

음수 값을 갖지 않고 함수축에 대칭인 함수를 선택하는 단계;Selecting a function that does not have a negative value and is symmetric about the function axis;

변수 구간을 적어도 3개의 구간으로 나누어 각 구간별로 상기 함수에 근사 하는 선형 함수를 선택하는 단계; Dividing the variable interval into at least three intervals and selecting a linear function approximating the function for each interval;

입력되는 두개의 메시지의 값을 연산하여 구한 두개의 값이 상기 변수 구간 가운데 어디에 속하는지 구분하는 단계;Calculating where two values obtained by calculating values of two input messages belong to one of the variable periods;

상기 구간에 대응하는 상기 선형 함수를 연산하여 두개의 함수값을 구하는 단계;Calculating two function values by calculating the linear function corresponding to the interval;

상기 두개의 함수값의 차를 출력하는 단계를 포함하여 이루어지는 것을 특징으로 한다.And outputting the difference between the two function values.

바람직하게, 상기 입력되는 두개의 메시지의 값을 연산하는 방법은 그 합과 차의 절대값을 취하는 것을 특징으로 한다.Preferably, the method for calculating the value of the two input messages is characterized by taking the absolute value of the sum and the difference.

바람직하게, 입력되는 새로운 메시지의 값과 상기 출력되는 함수값의 차를 연산하여 구한 두개의 값이 상기 변수 구간 가운데 어디에 속하는지 구분하는 단계; 상기 구간에 대응하는 상기 선형 함수를 연산하여 두개의 함수값을 구하는 단계; 상기 두개의 함수값의 차를 출력하는 단계를 포함하여 이루어지는 것을 특징으로 한다.Preferably, the step of distinguishing between the two values obtained by calculating the difference between the value of the new message input and the output function value belongs to the variable interval; Calculating two function values by calculating the linear function corresponding to the interval; And outputting the difference between the two function values.

바람직하게, 상기 음수 값을 갖지 않고 함수축에 대칭인 함수는 ln(cosh(x) 인 것을 특징으로 한다.Preferably, a function symmetrical to the function axis without the negative value is ln (cosh (x)).

바람직하게, 상기 함수에 근사하는 선형 함수는 상기 변수 구간 또는 각 구간 내에서의 함수 값이, 상기 음수 값을 갖지 않고 함수축에 대칭인 함수와의 오차가 최소가 되는 값인 것을 특징으로 한다.Preferably, the linear function approximating the function is characterized in that the value of the function within the variable section or each section is a value that minimizes an error with a function symmetrical to the function axis without having the negative value.

바람직하게, 상기 함수를 근사하기 위해 선택된 선형 함수는 을 적용한 것을 특징으로 한다.Preferably, the linear function selected to approximate the function is It is characterized by applying.

바람직하게, 근사식은 정해진 구간에 대해 근사화 함수와 최소 오차를 갖는 양자화 값을 갖는 것을 특징으로 한다.Preferably, the approximation formula is characterized by having an approximation function and a quantization value having a minimum error for a predetermined interval.

바람직하게, 상기 각 구간에 대응하는 근사식의 값은, 두 개의 입력 메시지의 값이 입력되면 두 메시지의 합과 차의 절대값을 각각 구하는 단계; 상기 구해진 두 개의 값에 대한 1/2값을 구한 다음, 이 값이 어느 구간에 해당하는지 비교한 후, 각 구간에 해당되는 근사식의 값을 얻는 단계를 포함하는 것을 특징으로 한다.Preferably, the value of the approximate expression corresponding to each interval may include obtaining an absolute value of the sum and the difference between the two messages when the values of the two input messages are input; Obtaining a 1/2 value for the two values obtained, and comparing the value to which section, and then obtains the value of the approximate equation corresponding to each section.

바람직하게, 상기 근사식을 이용해 구한 값을 최소합 함수에 재귀적으로 적용하는 것을 특징으로 한다.Preferably, the value obtained using the approximation formula is recursively applied to the minimum sum function.

바람직하게, 상기 각 구간별로 상수값 또는 일차 선형함수와 근사식 이 적용되는 구간 사이를 나누기 위한 기준 값이 서로 상이한 것을 특징으로 한다.Preferably, a constant value or a linear linear function and an approximation equation for each section The reference value for dividing between the sections to be applied is characterized in that they are different from each other.

상기와 같은 본 발명에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 대하여 첨부된 도면을 참조하여 설명하면 다음과 같다.Referring to the accompanying drawings, a method for decoding an error correcting code using an approximation function according to the present invention is as follows.

근사식을 이용한 복호 방법은 근사화 함수에 선형 함수 또는 양자화를 통하여 근사식을 구하고, 구한 근사식을 복호에 적용하여, 성능의 열화를 최소화하고 연산을 단순화하고, 또한 룩업 표가 필요없도록 한 것이다.The decoding method using the approximation formula is to obtain an approximation formula through a linear function or quantization to the approximation function, and apply the obtained approximation formula to the decoding, thereby minimizing performance degradation, simplifying the operation, and eliminating the need for a lookup table.

먼저, 디지털 데이터 수신을 위한 함수는 음의 값을 갖지 않고 원점을 지나며, y축에 대칭인 구조를 갖는 함수로서, 의 범위에서 (Min-Sum Algorthm)에 수렴하는 성질을 갖는다. 즉, 근사화 함수는 변수의 절대값 크기가 어느 정도 커지게 되면 선형함수 에 수렴하고, 변수의 절대값 크기가 작은 경우에는 상기의 근사식이 맞지 않으므로 상수값 또는 일차 선형 함수, 또는 함수의 양자화를 통해서 근사화하여 사용하게 된다.First, a function for receiving digital data is a function having a structure symmetrical on the y axis, passing through the origin without having a negative value. In the range of It has the property of converging to (Min-Sum Algorthm). In other words, the approximation function is a linear function when the absolute value of the variable increases to some extent. If the absolute value of the variable is small and the above approximation is not correct, it is approximated through a constant value, linear linear function, or quantization of the function.

이는, 최소합 알고리즘의 경우는 근사화 함수를 전 구간에서 로 생각함으로써, 변수의 절대값이 작은 부분에 대한 근사식의 적용이 복호 성능의 열화를 가져오게 된다.In the case of the minimum sum algorithm, the approximation function is By considering, the application of the approximation to the small absolute value of the variable leads to deterioration of the decoding performance.

여러 가지의 근사화 방법 중에서 연산의 단순화와 룩업 표의 필요성을 제거할 수 있도록, 선형 함수와 양자화를 통해서 근사화하고자 한다. 이를 위해, 선형 함수를 이용하여 근사화 함수를 몇 개의 구간으로 나누어 근사화하는 방법을 설명하고자 한다. In order to eliminate the necessity of simplification and lookup table among various approximation methods, we will approximate through linear function and quantization. To this end, a method of approximating the approximation function by dividing it into several intervals using a linear function will be described.

각 실시 예로서, 근사화 함수를 3구간과 4구간, 그리고 5구간 등으로 나누어 근사화 하는 방법을 제안한다. 즉, 근사화 함수를 3구간으로 나눌 때에는 특정 범위내에서는 상수 값을 갖고, 4구간 및 5구간으로 나눌 때에는 특정 범위 내에서 상수 값이나 일차 선형 함수로 나타난다. 여기서, 각 구간이나 그 구간 내에서의 함수 값은 약간씩 다를 수는 있으나 기본적으로 원 함수인 근사화 함수와의 오차를 최소화하는 값이다.As an example, a method of approximating the approximation function by dividing it into three sections, four sections, and five sections is proposed. That is, when dividing the approximation function into three sections, it has a constant value within a specific range, and when dividing into four sections and five sections, the approximation function is represented as a constant value or a linear linear function within a specific range. Here, the function value in each section or the section may be slightly different, but it is a value that minimizes an error from an approximation function that is a primitive function.

도 1은 제 1실시 예로서, 3구간의 선형 근사식이다. 도 1은 어느 특정 구간(범위) 내에서 상수 값을 가지며, 그 외의 값에 대해서는 식을 적용하는 근사식이다.1 is a linear approximation equation of three sections as a first embodiment. 1 has a constant value within a certain interval (range), and for other values This is an approximation to apply the equation.

먼저, 두 개의 입력 메시지( )의 값이 들어오면 두 메시지의 합과 차의 절대값을 각각 구한다. 즉, 두 메시지의 합의 절대값은 이고, 두 메시지의 차의 절대값은 이 된다.Firstly, two input messages ( ), The sum of the two messages and the absolute value of the difference are obtained. In other words, the absolute value of the sum of two messages The absolute value of the difference between the two messages is Becomes

이렇게 구한 두 개의 값의 1/2 값을 구하고, 구해진 값이 어느 구간에 해당되는 지 비교하며, 각 구간에 해당되는 근사식의 값을 얻는다. 즉, 어떤 값의 1/2은 비트 이동 연산을 통해서 쉽게 구할 수 있다. The half value of the two values obtained is obtained, the result is compared to which section, and the approximate value corresponding to each section is obtained. That is, 1/2 of a value can be easily obtained through bit shift operation.

즉, 도 1에서 구해진 근사식의 값들이 0.858 보다 작으면 상수 값 0.165로 취급되고, 만일 0.858보다 크게 되면 값을 따르게 된다. 이 구간의 범위는 상황에 따라 조금씩 바뀔 수 있다. 이를 수학식으로 나타내면 수학식 3과 같다.That is, if the values of the approximation equations obtained in FIG. 1 are smaller than 0.858, they are treated as a constant value of 0.165. Will follow the value. The range of this section may change slightly depending on the situation. This is represented by Equation 3 below.

=0.165 = 0.165

상기와 같이 근사식을 이용해 구한 값을 함수(수학식 1)에 그대로 적용하면, 최종적으로 얻어지는 출력 값이 원하는 메시지 값이다. 즉, 최종 메시지 값은 복호 알고리즘에서 심볼 노드, 체크 셋 노드에서의 확률 값에 해당하는 값이 된다.Using the approximation formula as above When applied to the function (Equation 1) as it is, the final output value is the desired message value. That is, the final message value is a value corresponding to a probability value of a symbol node and a check set node in the decoding algorithm.

여기서, 입력이 여러 개라면 근사식을 이용해 구한 값을 함수에 적용하여 얻은 출력 값과 다시 처음 과정부터 재귀적으로 사용하여 원하는 출력값을 얻게 된다.Here, if there are multiple inputs, the value obtained using the approximation The output value obtained by applying it to the function and then recursively used from the first step to obtain the desired output value.

즉, 입력이 4개라면 제 1 및 제 2입력 메시지에 대해 근사식을 이용하여 구한 값을 체크 함수에 적용한 제 1출력값과, 상기 제 1 출력값과 다른 제 3입력 메시지 값()과의 체크 함수[]의 얻는 제 2출력값과, 상기 제 2출력값과 제 4입력값()과의 체크 함수에 적용한 제 3출력값으로 구하게 된다.That is, if there are four inputs, a check function is obtained by using an approximation expression for the first and second input messages. A first output value applied to the third input message value different from the first output value ( ) And check function [ ], The second output value and the second output value and the fourth input value ( Function with The third output value applied to is obtained.

이를 수식으로 표현하면, 과 같은 작업을 반복한다.If you express it as a formula, Repeat the same operation.

이와 같이, 3구간으로 나누어 구한 근사식의 경우는 상기와 같이 단순히 일정한 상수 값이나 메시지의 절대 값에 을 뺀 값을 함수 값으로 갖고, 또한 덧셈과 뺄셈, 그리고 비교 연산만으로 이루어지므로 복호 연산이 전체적으로 단순해 진다. 즉, 최소합 알고리즘에 비해 연산에 관한 복잡도는 크게 증가하지는 않치만 원래 함수와의 최대 오차는 줄어들면서 더 정확한 값을 갖게 된다.In this case, the approximate expression obtained by dividing into three sections is simply applied to a constant constant value or an absolute value of the message as described above. Since the subtraction is a function value and only addition, subtraction, and comparison operations are performed, the decoding operation is simplified as a whole. In other words, compared to the minimum sum algorithm, the computational complexity does not increase significantly, but the maximum error with the original function is reduced, and thus more accurate value is obtained.

따라서, 근사화 함수를 근사화하지 않고 그대로 사용하는 복호 규칙 대신에 위에서 구한 근사식을 사용하게 되면 단순히 기울기에 해당하는 상수 곱셈이나 특정 구간에서만 갖는 상수 값으로만 연산이 이루어지므로 별도의 룩업 표가 필요 없게 된다. Therefore, if you use the above approximation formula instead of the decoding rule that does not approximate the approximation function, you do not need a separate lookup table because the operation is performed only by a constant multiplication corresponding to the slope or a constant value only in a specific section. do.

한편, 도 2를 참조하여, 4구간으로 나누어 구한 근사식의 경우에 대해 설명한다.On the other hand, with reference to FIG. 2, the case of the approximation formula obtained by dividing into 4 sections is demonstrated.

도 2에 의하면, 근사식의 값들이 1.185 보다 작을 경우 그 값이 0.40625=0.01101₍₂₎의 상수를 곱한 값으로 취급한다. 근사식의 값이 1.185 보다 크게 되면 값을 따르게 된다. 여기서, 상수 곱셈은 적당한 비트 이동 연산과 합 연산으로 바꿀 수 있다. 도 2에 의한 4구간의 근사식은 수학식 4와 같다.According to Fig. 2, when the values of the approximation expression are smaller than 1.185 _, the value is treated as a value multiplied by a constant of 0.40625 = 0.011 ₍₂₎ . If the value of the approximation is greater than 1.185 Will follow the value. Here, the constant multiplication can be changed into an appropriate bit shift operation and a sum operation. An approximation equation of four sections according to FIG. 2 is shown in Equation 4.

여기서, 0.40625=0.01101₍₂₎에 해당한다.Here, 0.40625 = 0.011 ₍₂₎ .

근사식을 이용해 구한 이 값을 함수에 그대로 적용하고, 만일 입력이 여러개 라면 상기 CHK 함수를 거쳐서 얻은 출력과 다시 처음 작업을 반복한다. 즉, 등과 같은 작업을 반복한다.This value obtained using the approximation Apply the function as is, and if there are multiple inputs, repeat the first operation with the output obtained through the CHK function. In other words, Repeat the same action.

이러한 근사식을 이용해 구한 값을 체크 함수에 그대로 적용한 후, 최종적으로 얻어지는 출력 값이 원하는 메시지 값이다. 이러한 최종 메시지 값은 복호 알고리즘에서 심볼 노드, 체크 셋 노드에서의 확률 값에 해당하는 값이 된다.After applying the value obtained using this approximation to the check function, the final output value is the desired message value. This final message value is a value corresponding to a probability value in a symbol node and a check set node in the decoding algorithm.

도 1과 같이 3구간으로 나누어 구한 근사식을 이용하는 경우와 도 2와 같이 4구간으로 나누어 구한 근사식을 이용한 경우의 차이점은 바로 상수 곱셈의 연산이 발생한다는 점이다. 더 정밀하게 근사화함으로써, 원래 함수와의 최대 오차의 값은 감소하여 더 좋은 성능을 기대할 수 있다. 또한 상수 곱셈이 발생하더라도 룩-업 표는 필요하지 않는다.The difference between using an approximation formula obtained by dividing into 3 sections as shown in FIG. 1 and using an approximation formula obtained by dividing into 4 sections as shown in FIG. 2 is that the operation of constant multiplication occurs. By more precise approximation, the value of the maximum error with the original function can be reduced to expect better performance. Also, look-up tables are not needed if constant multiplication occurs.

한편, 도 3은 본 발명 실시 예에 따른 5구간 선형 근사식이다. On the other hand, Figure 3 is a five-section linear approximation formula according to an embodiment of the present invention.

이렇게 구한 두 개의 값의 1/2 값을 구하고, 구해진 값이 5구간 중 어느 구간에 해당되는 지 비교하며, 각 구간에 해당되는 근사식의 값을 얻는다. 즉, 어떤 값의 1/2은 비트 이동 연산을 통해서 쉽게 구할 수 있다. The half value of the two values obtained is obtained, the result is compared to which section of the five sections, and the approximate value corresponding to each section is obtained. That is, 1/2 of a value can be easily obtained through bit shift operation.

각 구간별로 나타난 함수식은 수학식 5과 같다.The functional expression shown in each section is shown in Equation 5.

= 0.0398 = 0.0398

여기서, 0.71875는 0.10111₍₂₎에 해당한다.Here, 0.71875 corresponds to 0.10111 ₍₂₎ .

수학식 5와 같이 근사식의 값이 1.602 보다 크면 에 수렴하므로 두 구간(1구간, 5구간)에 적용하며, 근사식의 값이 1.602 보다 작고 0.404 보다 클 경우에는 를 이용하여 두 구간에 적용하며, 근사식의 값이 이면 0.0398의 상수 값을 가운데 한 구간에 적용한다.If the value of the approximation is greater than 1.602, as in Equation 5 Because it converges to, it is applied to two sections (1 section, 5 sections), and if the approximate value is less than 1.602 and larger than 0.404, Is applied to the two intervals using , Then apply a constant value of 0.0398 to one of the middle sections.

그리고, 근사식을 이용해 구한 이 값을 함수에 그대로 적용하고, 만일 입력이 여러 개라면 상기 CHK 함수를 거쳐서 얻은 출력과 다시 처음 작업을 반복한다. 즉, 등과 같은 작업을 반복한다.And, using this approximation The same applies to the function, and if there are multiple inputs, the output obtained through the CHK function is repeated with the first operation. In other words, Repeat the same action.

도 4는 5구간의 양자화 근사식이다.4 is an approximation equation of five sections.

각 구간별로 양자화된 함수식은 수학식 6과 같다.The function quantized for each section is shown in Equation 6.

= 0.2174 = 0.2174

= 0.1357 = 0.1357

즉, 근사식의 값이 0.965 보다 작을 경우에는 을 제 1 및 제 5 구간에 적용하고, 근사식의 값이 에 해당하면 양자화 값 0.2174을 제 2 및 제 4구간에 적용하며, 근사식의 값이 에 해당하면 양자화 값 0.1357을 제 3구간에 적용한다.That is, if the value of the approximation is less than 0.965 Is applied to the first and fifth intervals, and the approximate value is If the quantization value 0.2174 is applied to the second and fourth intervals, the approximate value is If, quantization value 0.1357 is applied to the third section.

이러한 양자화를 이용한 근사식은 각 구간의 모든 값을 일정한 상수 값으로 하는 근사식을 이용하면 룩업 표가 필요 없으며, 연산의 방법도 덧셈과 뺄셈, 비교 연산과 같은 간단한 연산만이 필요하게 된다. 이러한 양자화 방법은 여러 구간으로 나눈다 하여도, 어느 구간에 해당하는 값인지를 판단하기 위한 비교 연산만이 증가할 뿐 다른 연산에 관한 복잡도는 증가하지 않게 된다.The approximation formula using the quantization does not need a lookup table using an approximation formula in which all values of each interval are constant values, and also requires simple operations such as addition, subtraction, and comparison operations. Even if the quantization method is divided into several sections, only a comparison operation for determining which section corresponds to a value increases, but the complexity of other operations does not increase.

상술한 바와 같이 본 발명에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 의하면, 첫째, 합곱 알고리즘을 사용하는 기존의 알고리즘을 고려했을 때 근사화하지 않는 메시지 사이의 관계식을 이용한 복호 방법은 tanh(x) 또는 ln(cosh(x))의 계사을 위해 정밀한 룩업 표가 필요하므로, 많은 메모리가 필요하지만, 근사식을 사용하면 이러한 룩업 표가 필요 없게 되어 따라 메모리가 요구되지 않는다. As described above, according to the decoding method of an error correcting code using an approximation function according to the present invention, first, considering a conventional algorithm using a sum product algorithm, the decoding method using a relation between messages not approximated is tanh ( Precise lookup tables are required for the coercion of x) or ln (cosh (x)), which requires a lot of memory, but the approximation eliminates the need for such lookup tables and thus no memory.

둘째, 최소합 알고리즘을 사용하는 기존의 알고리즘에 비해 연산의 복잡도는 증가하지 않으나 더 뛰어난 성능을 갖는다. 특히 양자화를 이용한 근사식을 이용하는 경우는 여러 구간으로 나누어 더 정밀한 근사식을 얻는다 하여도 연산의 간단함에는 변함 없다. Second, compared to the conventional algorithm using the minimum sum algorithm, the computational complexity does not increase, but it has better performance. In particular, in the case of using an approximation equation using quantization, even if a more accurate approximation equation is obtained by dividing into several sections, the simplicity of the operation is not changed.

도 1은 본 발명 실시 예에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 있어, 3구간 선형 근사식을 도시화한 도면.1 is a diagram illustrating a three-section linear approximation equation in a method of decoding an error correcting code using an approximation function according to an exemplary embodiment of the present invention.

도 2는 본 발명 실시 예에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 있어, 4구간의 선형 근사식을 도식화한 도면.2 is a diagram illustrating a linear approximation equation of four sections in a method of decoding an error correcting code using an approximation function according to an exemplary embodiment of the present invention.

도 3은 본 발명 실시 예에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 있어, 5구간의 선형 근사식을 도식화한 도면.3 is a diagram illustrating a linear approximation equation of five sections in a method of decoding an error correcting code using an approximation function according to an exemplary embodiment of the present invention.

도 4는 본 발명 실시 예에 따른 근사화 함수를 사용하는 오류정정부호의 복호 방법에 있어, 5구간 양자화 근사식을 나타낸 도면.4 is a diagram illustrating a 5-section quantization approximation equation in a method of decoding an error correcting code using an approximation function according to an exemplary embodiment of the present invention.

Claims

In the digital data receiving apparatus,

Selecting a function that does not have a negative value and is symmetric about the function axis;

Dividing the variable interval into at least three intervals and selecting a linear function approximating the function for each interval;

Calculating the absolute values of the sums and differences of the two input messages and calculating the absolute values of the two messages and distinguishing the two values belonging to the variable intervals ;

Obtaining two function values after performing calculation using the selected linear function corresponding to the divided variable intervals ;

And outputting the difference between the obtained two function values .

The method of claim 1,

The method of decoding an error correcting code using an approximation function, wherein the desired output value is obtained by recursively using an output value obtained by applying an approximation expression to a check function when there are two or more inputs .

The method of claim 1,

Discriminating where two values obtained by calculating a difference between the input new message value and the output function value belong to one of the variable intervals;

Calculating two function values by calculating the linear function corresponding to the interval;

And outputting the difference between the two function values.

The method of claim 1,

And a function symmetrical on the function axis without the negative value is ln (cosh (x)).

The method of claim 1,

The linear function approximating the function uses an approximation function, characterized in that the value of the function in the variable section or each section is a value that minimizes an error with a function symmetrical in the function axis without having the negative value. How to Decrypt Error Correction Codes.

The method according to claim 1 or 5,

The linear function chosen to approximate the function A method of decoding an error correcting code using an approximation function, which is applied.

The method of claim 1,

Wherein the approximation equation has an approximation function and a quantization value having a minimum error for a predetermined section.

The method of claim 1,

The value of the approximation equation corresponding to each section is

Obtaining the absolute value of the sum and difference of the two messages, respectively, when the values of the two input messages are input;

Obtaining a 1/2 value for the two values obtained, and comparing the value corresponds to which section, and then using the approximation function comprising the step of obtaining an approximate value corresponding to each section Decoding method of error correcting code.

The method of claim 6,

A method of decoding an error correcting code using an approximation function, which recursively applies a value obtained using the approximation expression to a minimum sum function.

The method of claim 6,

Constant or linear linear function and approximate equation for each section A method of decoding an error correcting code using an approximation function, characterized in that the reference values for dividing between the sections to be applied are different from each other.