KR100212829B1 - Syndrome Calculator of Reed Solomon Decoder - Google Patents
Syndrome Calculator of Reed Solomon Decoder Download PDFInfo
- Publication number
- KR100212829B1 KR100212829B1 KR1019960005446A KR19960005446A KR100212829B1 KR 100212829 B1 KR100212829 B1 KR 100212829B1 KR 1019960005446 A KR1019960005446 A KR 1019960005446A KR 19960005446 A KR19960005446 A KR 19960005446A KR 100212829 B1 KR100212829 B1 KR 100212829B1
- Authority
- KR
- South Korea
- Prior art keywords
- syndrome
- symbol
- input
- shift register
- adder
- Prior art date
- Legal status (The legal status 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 status listed.)
- Expired - Fee Related
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, 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/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error 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/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, 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/65—Purpose and implementation aspects
- H03M13/6502—Reduction of hardware complexity or efficient processing
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, 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/65—Purpose and implementation aspects
- H03M13/6508—Flexibility, adaptability, parametrability and configurability of the implementation
- H03M13/6516—Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields
Landscapes
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
본 발명은 리드 솔로몬 복호기의 신드롬 계산장치에 관한 것으로, 수신 심볼(r1)을 중간값과 차례대로 더하여 출력하는 갈로아체 덧셈기(30)와 ; 상기 갈로아체 덧셈기(30)에서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 출력하는 중간값용 시프트 레지스터(40) ; 코드 워드의 마지막 수신 심볼(r0)또는 마지막에서 두 번째 심볼(r1)이 입력되는 기간에 상기 갈로아체 덧셈기(30)에서 출력된 값을 선택하여 출력하는 신드롬 선택부(50) ; 상기 신드롬 선택부(50)에서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 신드롬으로서 출력하는 신드롬용 시프트 레지스터(60) ; 코드워드의 마지막 수신 심볼(r0)이 입력되는 기간에 상기 신드롬용 시프트 레지스터(60)에서 출력된 값을 선택하여 출력하는 피트백 선택부(70) ; 한 심볼 클럭 사이클 동안에 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 입력하는 근 입력부(80) 및 ; 상기 피드백 선택부(70)에서 출력된 값과 상기 근 입력부(80)에서 입력된 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 곱하여 중간값을 상기 갈로아체 덧셈기(30)로 입력하는 갈로아체 곱셈기(90)을 포함하여 구성되어, 한 개의 갈로아체 덧셈기와 갈로아체 곱셈기를 가지는 신드롬 계산셀이 다수개의 신드롬을 동시에 계산함에 따라 신드롬 계산장치의 구조를 단순화시킬 수 있을 뿐만 아니라 전체 면적이 감소하여 신드롬 계산장치를 초 대규모 집적회로(VLSI)로 구현하기 용이한 것이다.The present invention relates to a syndrome calculation device of a Reed Solomon decoder, comprising: a galloche adder (30) which adds a reception symbol (r 1 ) and sequentially outputs the received symbol (r 1 ); An intermediate shift register 40 for shifting the value output from the galloche adder 30 according to a bit clock bit_clk; A syndrome selecting unit 50 for selecting and outputting a value output from the galloese adder 30 in a period in which the last received symbol r 0 or the last second symbol r 1 of the code word is inputted; A shift shift register (60) for shifting the value output from the syndrome selector (50) in accordance with a bit clock (bit_clk) to output as a syndrome; A pitback selector 70 for selecting and outputting a value output from the syndrome shift register 60 in a period during which the last received symbol r 0 of the codeword is input; A root input unit 80 which sequentially inputs the roots a 0 to a 7 of the plurality of code generation polynomials g (x) during one symbol clock cycle; The galloise adder multiplies the values output from the feedback selector 70 and the roots (a 0 to a 7 ) of the plurality of code generation polynomials g (x) input from the root input unit 80 in order. It is configured to include a Galoache multiplier (90) input to the (30), the syndrome calculation cell having one galoache adder and the Galoache multiplier can simplify the structure of the syndrome calculation device as a plurality of syndromes are simultaneously calculated In addition, the total area is reduced, making it easy to implement a syndrome calculator in a very large integrated circuit (VLSI).
Description
제1도는 일반적인 리드 솔로몬 복호기의 개략적인 구성도.1 is a schematic configuration diagram of a typical Reed Solomon decoder.
제2도는 종래의 신드롬 계산장치의 회로도.2 is a circuit diagram of a conventional syndrome calculation device.
제3도는 종래의 신드롬 계산셀의 회로도.3 is a circuit diagram of a conventional syndrome calculation cell.
제4도는 리드 솔로몬 복호기에 사용되는 심볼 클럭과 비트 클럭이 타이밍도.4 is a timing diagram of a symbol clock and a bit clock used in a Reed Solomon decoder.
제5도는 본 발명에 따른 리드 솔로몬 복호기의 신드롬 계산셀의 회로도.5 is a circuit diagram of a syndrome calculation cell of the Reed Solomon decoder according to the present invention.
제6도는 본 발명에 따른 제1 코드워드 종료신호 및 제2 코드워드 종료신호의 타이밍도이다.6 is a timing diagram of a first codeword end signal and a second codeword end signal according to the present invention.
* 도면의 주요부분에 대한 부호의 설명* Explanation of symbols for main parts of the drawings
1 : 선입 선출 버퍼 3 : 신드롬 계산부1: first-in, first-out buffer 3: syndrome calculation unit
5 : 에러 위치 다항식 계산부 7 : 에러 정정부5: error position polynomial calculation unit 7: error correction unit
9 : 제어부 30 : 갈로아체 덧셈기9: control unit 30: Galoache adder
40 : 중간값용 시프트 레지스터 50 : 신드롬 선택부40: shift register for intermediate values 50: syndrome selector
52 : 논리합 게이트 54 : 제1롬52: logical sum gate 54: first ROM
56 : 제1다중화기 60 : 신드롬용 시프트 레지스터56: first multiplexer 60: shift register for syndrome
70 : 중간값 선택부 72 : 제2다중화기70: intermediate value selector 72: second multiplexer
80 : 근 입력부 82 : 제2롬80: root input 82: second ROM
84 : 제3 다중화기 90 : 갈로아체 곱셈기84: third multiplexer 90: galloise multiplier
본 발명은 리드 솔로몬 부호기(Reed solomon encodor : RS encoder)에 의해 에러 정정 부호화(error correcting coding, error control coding : 이하 ECC라 칭함)된 디지털 데이터를 에러 정정 복호화하는 리드 솔로몬 복호기에 관한 것으로, 특히 신드롬을 계산하는 신드롬 계산셀을 비트 클럭에 의해 동작되도록 구현함으로써 그 구조가 간단한 리드 솔로몬 복호기의 신드롬 계산장치에 관한 것이다.BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Reed Solomon decoder for error correcting and decoding digital data subjected to error correcting coding (ECC) by a Reed solomon encoder (RS encoder). The present invention relates to a syndrome calculation device of a Reed-Solomon decoder, which has a simple structure by implementing a syndrome calculation cell that calculates a value to operate by a bit clock.
일반적으로, 에러 정정 부호화(ECC)는 디지털 데이터를 통신 채널을통해 전송하거나 저장 매체에 저장시에 발생되는 에러를 검출 정정하기 위해 디지털 데이터를 부호화하는 것으로, 에러를 검출하거나 정정하는데 사용되는 데이터를 부가함으로써, 데이터의 신뢰도를 높이게 되는 것이다.In general, Error Correction Coding (ECC) encodes digital data to detect and correct an error occurring when transmitting digital data through a communication channel or storing in a storage medium, and adds data used to detect or correct an error. This increases the reliability of the data.
이러한 에러 정정 코드(ECC)의 역사는 1948년 샤논(Claude Shannon)에서 부터 시작되었다. 샤논(Claude Shannon)은 1948년 모든 통신 채널은 C(bps)라고하는 고유의 전송 용량을 갖고 있으며 그 용량을 초과하지 않는 전송 속도 R(bps)로 데이터를 전송하는 통신 시스템을 구축하는 것은 에러 정정 부호를 이용하면 어떤 채널이고 가능하다는 것을 증명하였다. 즉, 아주 좋은 성능의 채널을 구현하는 것 보다 다소 성능이 떨어지는 기존 채널을 사용하면서 에러 정정부호를 사용하는 것이 더 경제적이라는 것이다.The history of this error correction code (ECC) began in 1948 with Shannon. In 1948, Shannon Shannon established a communication system that transmits data at a transmission rate R (bps), which has a unique transmission capacity of C (bps) and does not exceed that capacity. Using the sign proves which channel is possible. In other words, it is more economical to use an error correction code while using an existing channel that is somewhat inferior to implementing a very good channel.
그러나, 샤논(Claude Shannon)은 단지 에러 정정 코드가 존재한다는 것만을 증명하였을 뿐이며 에러 정정 코드를 찾는 방법에 대해서는 언급하지 않았다.However, Shannon only proved that an error correction code exists and did not mention how to find the error correction code.
이에 따라, 에러 정정 코드를 찾기 위한 노력이 현재까지 꾸준히 진행되고 있으며, 이러한 에러 정정 코드는 크게 블록 코드(block code)와 논블록 코드(nonblock code)로 나누어진다.Accordingly, efforts to find an error correction code have been steadily progressed up to now, and the error correction code is largely divided into a block code and a nonblock code.
상기 블록 코드는 정보 시퀀스를 k개의 비트로 이루어진 블록으로 분리한 다음 블록 단위로 에러 정정 부호하며, 상기 논블록 코드는 정보 시퀀스에 전체에 대해 에러 정정 부호화한다. 상기와 같은 블록 코드의 대표적인 예로는 BCH코드(Bose and Ray-Chaudhuri and Hocquenghem code)와 리드 솔로몬 코드(RS code)를 들 수 있고, 논블록 코드의 대표적인 예로는 길쌈 부호(convolutional code)를 들 수 있다.The block code divides the information sequence into blocks of k bits and then error corrects the code in block units. The non-block code encodes the entire information into the information sequence. Representative examples of such block codes include Bose codes (Bose and Ray-Chaudhuri and Hocquenghem code) and Reed Solomon codes (RS code), and representative examples of non-block codes are convolutional codes. have.
상기 BCH코드는 사이클릭(cyclic code)로서 갈로아체 GF(2m)상에서 동작된다. 사이클릭 코드란 선형 코드(liner code)의 어떤 선형 벡터를 사이클릭 시프트시키더라도 사이클릭 시프트된 선형 벡터가 상기 선형 코드의 선형 벡터인 선형 코드를 말한다.The BCH code is operated on Galoache GF (2 m ) as a cyclic code. A cyclic code refers to a linear code in which a cyclic shifted linear vector is a linear vector of the linear code, regardless of cyclic shift of any linear vector of the linear code.
따라서, BCH 코드는 하기 제1식과 같이 코드 발생 다항식 g(x)이 정해지면 피드백 시프트 레지스터를 이용하여 코드를 부호화할 수 있다.Therefore, the BCH code can be coded using the feedback shift register when the code generation polynomial g (x) is determined as in the following Equation 1 below.
이때, 상기 BCH 코드는 코드 발생 다항식 g(x)이 연속하는 2t개의 근을 가진다면 t개 까지의 에러는 정정할 수 있는 능력을 가진다.In this case, the BCH code has the ability to correct up to t errors if the code generation polynomial g (x) has two consecutive roots.
한편, 리드 솔로몬 코드는 상기 BCH 코드의 최적 코드로서 코드 발생 다항식이 상기 제1식과 같이 정해지면 t개의 에러를 정정할 수 있다.On the other hand, the Reed Solomon code is an optimal code of the BCH code and can correct t errors if the code generation polynomial is determined as in the first equation.
따라서, 현재 리드 솔로몬 코드는 통신 및 컴퓨터 기억 시스템 등에 폭 넓게 사용될 뿐만 아니라 재밍에 대항하기 위한 한 방법으로서 비밀 통신 시스템에서 사용되기도 한다.Accordingly, Reed Solomon codes are currently used not only widely in communication and computer storage systems, but also in secret communication systems as a way to combat jamming.
이와 같은 상기 리드 솔로몬 코드는 상기 BCH 코드와 마찬가지로 갈로아체 GF(2m) 상에서 동작된다. 즉, 상기 갈로아체 GF(2m)는 2m개의 원소를 갖는 수체계(number system)로서, 이러한 수체계를 하드웨어로 구현하게 되면 각 원소들이 모두 m개의 바이너리 디저트(digit)로 표현될 수 있으므로 디지탈 구조에 효과적일 뿐만 아니라 오버 플로우(over flow)가 발생하지 않게 되는 거이다.This Reed Solomon code is operated on Galoache GF (2 m ) like the BCH code. That is, the Galoache GF (2 m ) is a number system having 2 m elements. When the hardware system is implemented in hardware, each element may be represented as m binary desserts (digits). Not only is it effective for digital construction, but it does not cause overflow.
상기와 같이 갈로아체 GF(2m)상의 코드를 가지는 리드 솔로몬 코드는 정보와 패리티(parity)가 섞이지 않는 계통적 코드(systematic code)와 정보와 패리티(parity)가 섞이는 비계통적 코드(nonsystematic code)로 분류된다.Reed Solomon code having a code on Galoache GF (2 m ) as described above is a systematic code that does not mix information and parity, and a nonsystematic code that mixes information and parity. Are classified.
상기 계통적 코드는 정보와 패리티가 섞이지 않도록 우선 정보를 상위 바이트로 이동시킨 다음 에러 정정요 코드를 구하여 더한 것으로, 하기 제2식으로 부터 구해진다.The systematic code is obtained by first moving the information to an upper byte so as not to mix information and parity, and then obtaining an error correction request code, which is obtained from the following equation.
상기 제2식에 있어서, 상기 c(x)는 코드워드 다항식이고, i(x)는 정보 다항식이며, t(x)는 에러 정정용 패리티의 다항식이다.In the second equation, c (x) is a codeword polynomial, i (x) is an information polynomial, and t (x) is a polynomial of error correction parity.
즉, 정보와 패리티 섞이지 않게 정보 i(x)를 χN-K차 만큼 상위 바이트로 이동시킨 다음를 만족하는 패리티 t(x)를 구한다.That is, the information i (x) is moved to the higher byte by χ NK difference so as not to mix information and parity, Find the parity t (x) that satisfies.
그리고,을 만족하는 패리티 t(x)를 하기 제3식으로부터 구할 수 있다.And, The parity t (x) that satisfies can be obtained from the following equation.
상기에 있어서는 코드워드 다항식 c(x)를 코드 발생 다항식 g(x)로 나눈 나머지값을 의미한다.In the above Denotes the remainder of the codeword polynomial c (x) divided by the code generation polynomial g (x).
즉, 상기 패리티 t(x)를 구하기 위해서는 χN-Kⅰ(χ)를 코드 발생 다항식 g(x)로 나누는 과정을 수행하여야 하며 이러한 과정은 시프트 레지스터를 코드 발생 다항식 g(x)에 따라 연결하여 구현할 수 있다.In other words, in order to obtain the parity t (x), the process of dividing χ NK ⅰ (χ) by the code generation polynomial g (x) is performed by connecting the shift register according to the code generation polynomial g (x). Can be.
그리고, 상기 비계통적 코드는 하기 제4식과 같이 단순히 정보에 코드 발생 다항식 g(x)을 곱해 줌에 따라 정보와 패리티가 섞이게 된다.In the non-system code, information and parity are mixed by simply multiplying the information by the code generation polynomial g (x) as shown in Equation 4 below.
상기 제4식에서 c(x)는 n-1차의 코드워드 다항식이고, i(x)는 k-1차의 정보 다항식, g(x)는 n-k차의 코드 발생 다항식이다.In equation 4, c (x) is an n-1 order codeword polynomial, i (x) is an k-1 order information polynomial, and g (x) is an n-k order code generating polynomial.
상기 코드 발생 다항식 g(x)은 코드워드 다항식 c(x)를 만들어 내기 위해 정보 다항식 i(x)에 곱해지는 것으로, 이러한 코드 발생 다항식 g(x)을 하기 제5식과 같이 연속적인 2t개의 근을 가지도록 정하면 t개의 에러를 정정할 수 있다.The code generating polynomial g (x) is multiplied by the information polynomial i (x) to produce a codeword polynomial c (x). The code generating polynomial g (x) is multiplied by 2t roots as shown in Equation 5 below. If we set to have t errors, we can correct t errors.
상기와 같은 방법으로 리드 솔로몬 부호화된 디지털 데이터를 리드 솔로몬 복호화하는 방법은 크게 주파수 영역 복호화와 시간 영역 복호화로 나누어지며, 상기 시간 영역에서 리드 솔로몬 복호화하는 과정은 다음과 같이 크게 4단계로 이루어진다.Reed-Solomon decoding of Reed-Solomon-coded digital data as described above is largely divided into frequency-domain decoding and time-domain decoding, and the process of Reed-Solomon decoding in the time domain is largely performed in four steps as follows.
1)신드롬 계산1) Calculation of syndrome
수신된 데이터 r(x)는 하기 제6식과 같이 코드워드 다항식 c(x)과 전송중에 발생된 에러 다항식 e(x)를 더한 값으로 표현될 수 있다.The received data r (x) may be expressed as a sum of a codeword polynomial c (x) and an error polynomial e (x) generated during transmission, as shown in Equation 6 below.
따라서 , 하기 제7식과 같이 수신된 데이터 r(x)에 코드 발생 다항식 g(x)의 근 a0~a2t-1을 차례대로 대입함으로써 전송중에 에러가 발생되었는지를 알 수 있는 것이다.Therefore, it is possible to know whether an error has occurred during transmission by assigning the roots a 0 to a 2t-1 of the code generation polynomial g (x) in order to the received data r (x) as shown in Equation 7 below.
즉, 수신된 데이터 r(x)에 코드 발생 다항식 g(x)의 근 ai을 대입하여 수신된 데이터 r(x)가 0이 되면 전송중에 에러가 발생되지 않았다는 것을 의미하며, 수신된 데이터 r(x)에 코드 발생 다항식의 근 ai을 대입하여 수신된 데이터 r(x)가 0이 되지 않으면 i번째 위치 또는 i차에 에러가 발생하였다는 것을 의미한다.That is, when the received data r (x) becomes 0 by substituting the root a i of the code generation polynomial g (x) into the received data r (x), it means that no error occurred during transmission. If the received data r (x) does not become 0 by substituting root a i of the code generation polynomial in (x), it means that an error has occurred in the i th position or the i th order.
2) 에러 위치 다항식 계산(finding error location)2) Finding error location polynomial
Berlekamp-Massey 알고리즘 또는 Euclid 알고리즘으로부터 에러 위치 다항식의 계수를 계산한다.Compute the coefficients of the error location polynomials from the Berlekamp-Massey algorithm or the Euclid algorithm.
상기 알고리즘에 의해 구해진 에러 위치 다항식을(X)라 하면 에러 정정 능력인 t인 리드 솔로몬 코드에서는 하기 제8식과 같이 최고 t차 이하의 다항식이 얻어진다.The error position polynomial obtained by the above algorithm In the case of (X), a Reed Solomon code having an error correction capability of t obtains a polynomial of not more than the highest order, as shown in Equation 8 below.
3) 에러값 계산3) Error value calculation
상기 에러 위치 다항식(X)에 a-t을 대입하면 에러의 위치를 찾는다.The error location polynomial Substituting a -t for (X) finds the location of the error.
즉, 에러 위치 다항식(X)에 a-t을 대입하여 에러 위치 다항식(X)이 0이 되면 i번째 위치 또는 i차에 에러가 발생된 것이다.That is, the error-position polynomial Error location polynomial by substituting a -t for (X) If (X) becomes 0, an error occurs in the i th position or the i th order.
그리고, 에러 평가 다항식(X)은 하기 제9식으로부터 구할 수 있다.And error evaluation polynomial (X) can be calculated | required from the following 9th formula.
상기 제6식에서 S(X)는 신드롬 다항식이다.In Formula 6, S (X) is a syndrome polynomial.
이와 같이 에러 평가 다항식(X)을 구한 다음 하기 제10식으로부터 에러값 ei을 계산한다.Thus the error evaluation polynomial After calculating (X), the error value e i is calculated from the following equation.
상기 제10식에서는'는 에러 위치 다항식을 미분한 값이다.In the above formula 10 'Is the error position polynomial Is the derivative of.
4) 에러 정정4) Error correction
상기와 같이 에러값을 구한 다음 하기 제 11식을 이용하여 원래의 코드워드 다항식 c(x)를 구하는 것이다.After the error value is obtained as described above, the original codeword polynomial c (x) is obtained by using Equation 11 below.
이때, 갈로아체 특성상 같은 값을 더하면 0이 되므로 e(x)+ e(x)=0 이되는 것이다.At this time, if the same value is added to the characteristics of galloise becomes 0, e (x) + e (x) = 0.
한편, 상기와 같은 과정으로 이루어진 리드 솔로몬 복호화 방법을 하드웨어로 구현한 일반적인 리드 솔로몬 복호기는 제1도에 도시한 바와 같이, 리드 솔로몬 부호화된 수신 신호r(x)를 일시 저장하였다가 출력하는 선입선출버퍼(1)와 : 상기 리드 솔로몬 부호화된 수신 신호 r(x)로부터 신드롬 Si을 계산하여 출력하는 신드롬 계산부(3) : 상기 신드롬 Si을 입력받아 에러 위치 다항식(X)을 계산하여 출력하는 에러 위치 다항식 계산부(5) : 상기 신드롬 Si및 에러 위치 다항식(X)을 입력받아 에러 평가 다항식(X)을 구하는 한편 상기 에러 평가 다항식(X)으로부터 에러값 ei를 구하고, 상기 선입선출버퍼(1)에서 출력된 수신 신호 r(x)에 상기 에러값 ei을 더해 수신 신호r(x)에 발생된 에러를 정정하는 에러 정정부(7) 및 : 상기 신드롬 계산부(3)와 에러 위치 다항식 계산부(5) 및 상기 에러 정정부(7)를 각각 제어하는 제어부(9)를 포함하여 구성되어 있다.On the other hand, a general Reed Solomon decoder that implements the Reed Solomon decoding method as described above in hardware, as shown in FIG. 1, first-in, first-out of temporarily storing and outputting the Reed Solomon-coded received signal r (x). A buffer 1 and a syndrome calculator for calculating and outputting a syndrome S i from the Reed-Solomon-coded received signal r (x): The error position polynomial is obtained by receiving the syndrome S i . Error position polynomial calculation unit 5 for calculating and outputting (X): the syndrome S i and the error position polynomial Error evaluation polynomial with input of (X) (X) while the error evaluation polynomial An error value e i is obtained from (X), and the error value e i is added to the received signal r (x) output from the first-in first-out buffer 1 to correct the error generated in the received signal r (x). And a control unit 9 for controlling the syndrome calculation unit 3, the error position polynomial calculation unit 5, and the error correction unit 7, respectively.
상기 신드롬 계산부(3)는 수신 신호 r(x)를 입력받아 신드롬 Si을 계산하며, 이때 상기 상기 신드롬 계산부(3)는 하나의 코드 워드 c(x)가 모두 입력되어야만 신드롬 계산이 완료된다.The syndrome calculation unit 3 receives the received signal r (x) and calculates syndrome S i . At this time, the syndrome calculation unit 3 completes the syndrome calculation only when one code word c (x) is input. do.
그리고, 에러 위치 다항식 계산부(5)는 Berlekamp algorithm 이나 Euclid algorithm 등을 통하여 에러의 위치를 찾아낼 수 있는 다항식 즉 에러 위치 다항식(X)을 계산하여 에러 정정부(7)로 출력한다.In addition, the error position polynomial calculation unit 5 may determine a position of an error through a Berlekamp algorithm or Euclid algorithm, that is, an error position polynomial. (X) is calculated and output to the error correction unit 7.
그리고, 에러 정정부(7)는 상기 에러 위치 다항식(X)과 상기 신드롬 계산부(3)에서 출력된 신드롬 Si으로부터 에러 평가 다항식(X)을 구한 다음 상기 에러 평가 다항식(X)으로부터 에러값 ei을 구하여 상기 선입선출버퍼(1)에서 출력된 수신 신호 r(x)에 더해줌으로써 수신 신호 r(x)에 발생된 에러를 정정하여 에러 정정 복호화된 코드 워드 c(x)를 출력하는 것이다.Then, the error correction unit 7 is the error position polynomial Error evaluation polynomial from (X) and syndrome S i output from syndrome calculation section 3 (X) and then the error evaluation polynomial An error value e i is obtained from (X) and added to the received signal r (x) output from the first-in, first-out buffer 1 to correct an error generated in the received signal r (x), thereby correcting the error and decoding code word c ( x) is printed.
그리고, 상기 신드롬 계산부(3)는 제2도에 도시된 바와 같이, 리드 솔로몬복호화된 수신 신호 r(x)를 심볼 클럭(sym_clk)에 따라 래치시켜 수신 심볼(ri)을 차례대로 입력하는 레지스터(11)와, 상기 레지스터(11)를 통해 수신 심볼(ri)을 차례대로 입력받아 코드 발생 다항식 g(x)의 각 근(a0~a2t-1)에 대해 신드롬(S0~S2t-1)을 계산하는 다수개(2t개)의 신드롬 계산셀(13-1~13-2t)을 포함하여 구성되어 있다.As shown in FIG. 2, the syndrome calculator 3 latches the read- Solomon-decoded received signal r (x) according to the symbol clock sym_clk to sequentially input the received symbol r i . The register 11 and the receiving symbol r i are sequentially input through the register 11 and the syndrome S 0 to each root a 0 to a 2t-1 of the code generation polynomial g (x) is received. A plurality of (2t) syndrome calculation cells 13-1 to 13-2t for calculating S 2t-1 ) are included.
예를 들어, 리드 솔로몬 코드 (N, K)를 리드 솔로몬 복호화하는 리드 솔로몬 복호기에 사용되는 신드롬 계산부(3)에서는 N-K=2t개의 신드롬 계산셀(13-1~13-2t)이 필요하게 된다.For example, in the syndrome calculation unit 3 used in the Reed Solomon decoder for decoding Reed Solomon codes (N, K), NK = 2t syndrome calculation cells 13-1 to 13-2t are required. .
즉, N개의 심볼(한개의 코드 워드)을 입력받아 동시에 2t개의 신드롬(S0~S2t-1)을 각각 계산하는 것이다.That is, it receives N symbols (one code word) and calculates 2t syndromes S 0 to S 2t-1 at the same time.
이때, 상기 각 신드롬 계산셀(13-1~13-2t)은 하기 제12식 같은 신드롬 계산 공식을 하드웨어적으로 구현한 것이다.In this case, each of the syndrome calculation cells 13-1 to 13-2t is a hardware implementation of a syndrome calculation formula such as the following equation 12.
상기에서 rj는 수신 신호 r(x)가 심볼 클럭에 동기되어 입력된 수신 심볼을 의미한다.In the above, r j means a received symbol in which the received signal r (x) is input in synchronization with the symbol clock.
상기 제12식을 하드웨어적으로 구현한 각 신드롬 계산셀(13-1~13-2t)은 제3도에 도시된 바와 같이, 수신 심볼(ri)과 중간값을 더하여 출력하는 갈로아체 덧셈기(21)와 : 코드 발생 다항식 g(x)의 근(ai)이 저장되어 있는 롬(23) : 상기 갈로아체 덧셈기(21)에서 출력된 신호와 상기 롬(23)에 저장되어 있는 코드 발생 다항식 g(x)의 근(ai)을 곱하여 중간값을 출력하는 갈로아체 곱셈기(25)및; 상기 갈로아체 곱셈기(25)에서 출력된 중간값을 심볼 클럭(sym_clk)에 따라 래치시켜 상기 갈로아체 덧셈기(21)로 입력하는 레지스터(27)를 포함하여 구성되어 있다.As shown in FIG. 3, each syndrome calculation cell 13-1 to 13-2t, which implements the 12th equation in hardware, includes a galloise adder for adding the received symbol r i and the median value. 21) and Rom 23 in which the root (a i ) of the code generation polynomial g (x) is stored: the signal output from the Galoache adder 21 and the code generation polynomial stored in the ROM 23 a galloise multiplier 25 for multiplying the root a i of g (x) and outputting a median value; And a register 27 for latching the intermediate value output from the galloise multiplier 25 to the galloise adder 21 by latching the intermediate value according to the symbol clock sym_clk.
그러나, 상기와 같은 종래의 신드롬 계산장치는, 2t개의 신드롬(S0~S2t-1)을 계산하기 위한 신드롬 계산셀(13-1~13-2t)이 2t개 필요하고, 상기 각 신드롬 계산셀(13-1~13-2t) 마다 갈로아체 덧셈기(21)와 갈로아체 곱셈기(25)가 필요하므로, 전체적으로 갈로아체 덧셈기(21)와 갈로아체 곱셈기(25)가 2t개 만큼 필요하게 된다.However, in the conventional syndrome calculation device as described above, 2t syndrome calculation cells 13-1 to 13-2t for calculating 2t syndromes S 0 to S 2t-1 are required, and each syndrome calculation is performed. Since each of the cells 13-1 to 13-2t requires a galloa adder 21 and a galloa multiplier 25, as a whole, a galloa adder 21 and a galloa multiplier 25 are required.
따라서, 신드롬 계산장치의 구조가 복잡할 뿐만 아니라 신드롬 계산장치의 면적이 증가하여 초 대규모 집적회로(VLSI)로 구현하기 어려문 문제점이 있었다.Therefore, not only the structure of the syndrome calculation device is complicated, but also the area of the syndrome calculation device is increased, which makes it difficult to implement the ultra large-scale integrated circuit (VLSI).
따라서, 본 발명은 상기와 같은 종래의 제 문제점을 해소하기위한 것으로, 신드롬을 계산하는 신드롬 계산셀을 비트 클럭에 의해 동작되도록 구현함으로써 그 구조가 간단할 뿐만 아니라 면적이 감소된 리드 솔로몬 복호기의 신드롬 계산장치를 제공하는데 그 목적이 있다.Accordingly, the present invention is to solve the above-mentioned conventional problems, by implementing a syndrome calculation cell for calculating the syndrome to be operated by the bit clock, the structure of the Reed Solomon decoder with a simple structure as well as a reduced area The purpose is to provide a computing device.
이러한 목적을 달성하기 위한 본 발명에 따른 리드 솔로몬 복호기의 신드롬 계산장치는, 리드 솔로몬 복호화된 수신 신호를 심볼 클럭에 따라 래치시켜 수신 심볼을 차례대로 입력하는 레지스터와, 상기 레지스터를 통해 수신 심볼을 차례대로 입력받아 코드 발생 다항식의 각 근에 대해 신드롬을 계산하는 다수개의 신드롬 계산셀을 포함하여 구성된 신드롬 계산장치에 있어서, 상기 신드롬 계산셀이, 상기 레지스터를 통해 입력된 수신 심볼을 중간값과 차례대로 더하여 출력하는 갈로아체 덧셈기와 : 상기 갈로아체 덧셈기에서 출력된 값을 비트 클럭에 따라 시프트시켜 출력하는 중간값용 시프트 레지스터 : 코드 워드의 마지막 수신 심볼 또는 마지막에서 두 번째 심볼이 입력되는 기간에 상기 갈로아체 덧셈기에서 출력된 값을 선택하여 출력하는 신드롬 선택부 : 상기 신드롬 선택부에서 출력된 값을 비트 클럭에 따라 시프트시켜 신드롬으로서 출력하는 신드롬용 시프트 레지스터 : 코드 워드의 마지막 수신 심볼이 입력되는 기간에는 상기 신드롬용 시프트 레지스터에서 출력된 값을 선택하여 출력하는 피드백 선택부 : 한 심볼 클럭 사이클 동안에 다수개의 코드 발생 다항식의 근을 차례대로 입력하는 근 입력부 및 : 상기 피드백 선택부에서 출력된 값과 상기 근입력부에서 입력된 다수개의 코드 발생 다항식의 근을 차례대로 곱하여 중간값을 상기 갈로아체 덧셈기로 입력하는 갈로아체 곱셈기를 포함하여 구성된 것을 특징으로 한다.A syndrome calculation apparatus for a Reed Solomon decoder according to the present invention for achieving the above object comprises a register for latching a Reed Solomon decoded received signal according to a symbol clock to sequentially input a received symbol, and then sequentially receiving the received symbol through the register. A syndrome calculation device including a plurality of syndrome calculation cells for receiving syndromes and calculating syndromes for each root of a code generation polynomial, wherein the syndrome calculation cell sequentially receives a received symbol input through the register in an intermediate order. In addition, the output of the galloche adder: The shift register for the intermediate value for shifting the value output from the galloche adder according to the bit clock and outputting: During the period of receiving the last received symbol or the second to last symbols of the code word is input Select and print the output value from the adder A drop selector: A shift shift register for shifting a value output from the syndrome selector according to a bit clock to output as a syndrome: Select a value output from the shift shift register for a period when the last received symbol of a code word is input. A feedback selector for inputting the roots of a plurality of code generation polynomials sequentially during one symbol clock cycle; and a root of the plurality of code generation polynomials inputted from the feedback input unit and the root input unit. It is characterized in that it comprises a galoache multiplier for multiplying in order to input the intermediate value into the galloche adder.
즉, 한 개의 갈로아체 덧셈기와 갈로아체 곱셈기를 가지는 한 개의 신드롬 계산셀이 다수개의 신드롬을 동시에 계산할 수 있도록 되어, 갈로아체 덧셈기 및 갈로아체 곱셈기의 수를 줄일 수 있는 것이다.That is, one syndrome calculating cell having one galloa adder and a galloa multiplier can calculate a plurality of syndromes at the same time, thereby reducing the number of galloa adders and galloa multipliers.
따라서, 신드롬 계산장치의 구조를 단순화시킬 수 있을 뿐만 아니라 전체 면적이 감소하여 신드롬 계산장치를 초 대규모 집적회로(VLSI)로 구현하기 용이한 것이다.Therefore, not only can the structure of the syndrome calculation device be simplified, but the overall area is reduced, so that the syndrome calculation device can be easily implemented as a VLSI.
이하,첨부된 도면을 참조하여 본 발명의 실시예를 상세히 설명한다.Hereinafter, with reference to the accompanying drawings will be described embodiments of the present invention;
유럽 위성 디지탈 방송 구격인 DVB 스펙(spec)에서는 전송율이 약 60Mbps에 이르는데, 이를 심볼 클럭으로 환산하면 1심볼이 8비트로 구성되므로 전송율이 7.5Mbps가 된다. 즉, 제4도에 도시된 바와같이, 한 심볼 클럭(symbol clock)의 사이클(cycle)은 133.3nsec이고, 비트 클럭(bit clock)의 사이클은 상기 심볼 클럭의 1/8 인 16.67nsec이다.In the DVB spec, the European satellite digital broadcast target, the transmission rate is about 60 Mbps, which is converted into a symbol clock, so that one symbol consists of 8 bits, resulting in a transmission rate of 7.5 Mbps. That is, as shown in FIG. 4, the cycle of one symbol clock is 133.3 nsec, and the cycle of the bit clock is 16.67 nsec, which is 1/8 of the symbol clock.
한편, 리드 솔로몬 복호기의 신드롬 계산장치는 수신 신호를 상기와 같은 심볼 클럭(symbol clock)에 동기시켜 입력받아 신드롬을 계산한다.On the other hand, the syndrome calculation device of the Reed Solomon decoder receives the received signal in synchronization with the symbol clock (symbol clock) as described above to calculate the syndrome.
예를들어, 리드 솔로몬 코드 (N,K) 를 리드 솔로몬 디코딩하는 리드 솔로몬 디코더에서 쓰이는 신드롬 계산장치는 수신 신호를 심볼 클럭에 동기시켜 한 개의 코드 워드당 N개의 심볼로 입력 받아 2t개의 신드롬을 각각 계산하는 것이다. 이때, 신드롬을 계산하는 과정에서 시간적으로 가장 중요한경로(critical path)는 갈로아체 GF(2m)곱셈인데, 갈로아체 곱셈을 비트 클럭 사이클(약 16,67nsec)동안에 동작시킬 수만 있다면 심볼 클럭 대신에 비트 클럭을 사용할 수 있는 것이다.For example, the syndrome calculator used in the Reed Solomon decoder, which reads Reed Solomon code (N, K) from Reed Solomon, receives the received signal as N symbols per code word by synchronizing the received signal with the symbol clock and receives 2t syndromes. To calculate. At this time, the most important time path in calculating the syndrome is galloise GF (2 m ) multiplication, and if it is possible to operate Galoache multiplication for a bit clock cycle (approximately 16,67 nsec), instead of symbol clock The bit clock can be used.
상기와 같은 조건을 만족하는 갈로아체 GF(2m) 곱셈기는 이미 제안되었으며, 그 일예로는 동일 발명자에 의해 1995년 12월 28일자로 출원된 한국 특허 출원 번호 95-61391에 이미 제안된 갈로아체 GF(2m) 곱셈기를 들 수 있다.Galoache GF (2 m ) multipliers that meet the above conditions have already been proposed, for example Galoache already proposed in Korean Patent Application No. 95-61391 filed December 28, 1995 by the same inventor GF (2 m ) multipliers.
따라서, 상기와 같이 연산 속도가 빠른 갈로아체 GF(2m) 곱셈기를 사용하게되면, 신드롬 계산시에 비트 클럭을 사용할 수 있는 것이다.Therefore, when using the Galoache GF (2 m ) multiplier with a high operation speed as described above, it is possible to use the bit clock in the syndrome calculation.
즉, 제5도는 본 발명에 따른 신드롬 계산셀의 회로도로서, 입력된 수신심볼(ri)을 중간값(intermediate value)과 차례대로 더하여 출력하는 갈로아체 덧셈기(30)와 : 상기 갈로아체 덧셈기(30)에서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 출력하는 중간값용 시프트 레지스터(40) : 코드 워드의 마지막 수신 심볼(r0) 또는 마지막에서 두 번째 심볼(r1)이 입력되는 기간에 상기 갈로아체 덧셈기(30)에서 출력된값을 선택하여 출력하는 신드롬 선택부(50) : 상기 신드롬 선택부(50)에서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 신드롬(synd)으로서 출력하는 신드롬용 시프트 레지스터(60) : 코드 워드의 마지막 수신 심볼(r0)이 입력되는 기간에는 상기 신드롬용 시프트 레지스터(60)에서 출력된 값을 선택하여 출력하는 피드백 선택부(70) : 한 심볼 클럭 사이클 동안에 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 입력하는 근 입력부(80) 및 : 상기 피드백 선택부(70)에서 출력된 값과 상기 근 입력부(80)에서 입력된 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 곱하여 중간값을 상기 갈로아체 덧셈기(30)로 입력하는 갈로아체 곱셈기(90)를 포함하여 구성되어 있다.That is, FIG. 5 is a circuit diagram of a syndrome calculation cell according to the present invention. The Galoache adder 30 and outputting the received reception signal r i are sequentially added with an intermediate value. A shift register 40 for an intermediate value for shifting and outputting a value output from 30) according to a bit clock bit_clk: a period in which the last received symbol r 0 of the code word or the last second symbol r 1 is inputted. Syndrome selector 50 for selecting and outputting a value output from the galloche adder 30: Shifting the value output from the syndrome selector 50 in accordance with a bit clock (bit_clk) as a syndrome (synd). Syndrome shift register 60 for outputting: A feedback selector 70 for selecting and outputting a value output from the syndrome shift register 60 in a period during which the last received symbol r 0 of the code word is input. Symbol clock Roots of a plurality of code generating polynomial g (x) during the cycle (a 0 ~ a 7) to turn, enter near an input 80 and that: the value of the near-input section 80 is output from the feedback selector 70 It consists of a Galloiche multiplier 90 for multiplying the roots (a 0 to a 7 ) of a plurality of code generation polynomials g (x) inputted in order and inputting the median value into the Galois adder 30. .
상기 중간값용 시프트 레지스터(40)는 코드워드중 마지막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)를 리셋단자(rst)로 입력받아 리셋되도록 되어 있다.The intermediate shift register 40 receives a first codeword end signal cw_end1 which becomes 1 while the last symbol r 0 of the codeword is input to the reset terminal rst.
그리고, 상기 신드롬 선택부(50)는 코드워드중 마지막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)와 코드워드 중 마지막에서 두 번째 심볼(r1)이 입력되는 동안에 1되는 제2 코드워드 종료신호(cw_end2)를 논리합하여 출력하는 논리합게이트(52) : 0이 저장되어있는 제1롬(54) 및 : 상기 논리합게이트(52)에서 출력된 신호를 선택신호로 입력받아 상기 선택 신호에 따라 상기 제1 롬(54)에 저장되어 있는 0 또는 상기 갈로아체 덧셈기(30)에서 출력된 값을 선택적으로 출력하는 제1다중화기(56)를 포함하여 구성되어 있다.In addition, the syndrome selector 50 is input, the second symbol (r 1) at the end of the code words of the last symbol (r 0), the first codeword end signal (cw_end1) with codes of 1, while the input word A logic sum gate 52 for logically summing and outputting the second codeword end signal cw_end2 which is 1 during the operation; the first ROM 54 having 0 stored therein; and the signal output from the logic sum gate 52. And a first multiplexer 56 for selectively outputting 0 stored in the first ROM 54 or a value output from the galloche adder 30 according to the selection signal. .
그리고, 상기 제1다중화기(56)는 상기 선택신호가 1이면 상기 갈로아체 덧셈기(30)에서 출력된 값을 선택하여 출력하고, 상기선택신호가 0이면 상기 제1롬(54)에 저장되어 있는 0을 출력하도록 되어 있다.When the selection signal is 1, the first multiplexer 56 selects and outputs a value output from the galloche adder 30, and when the selection signal is 0, is stored in the first ROM 54. Output zeros.
그리고, 상기 피드백 선택부(70)는 코드워드중 마시막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)를 선택신호로 입력받아 상기 제1 코드워드 종료신호(cw_end1)가 1이면 상기 신드롬용 시프트 레지스터(60)에서 출력된 값을 선택하여 상기 갈로아체 곱셈기(90)로 입력하고, 상기 제1 코드워드 종료신호(cw_end1)가 0이면 상기 중간값용 시프트 레지스터(40)에서 출력된 값을 선택하여 상기 갈로아체 곱셈기(30)로 입력하는 제2다중화기(72)로 이루어져 있다.In addition, the feedback selector 70 receives the first codeword end signal cw_end1, which is 1, as the selection signal while the last symbol r 0 of the codewords is input as the selection signal. If cw_end1 is 1, a value output from the syndrome shift register 60 is selected and input to the galloche multiplier 90. If cw_end1 is 0, the intermediate value shift register (cw_end1) is 0; A second multiplexer 72 selects a value output from the input 40 and inputs the multiplier 30 to the galloche multiplier 30.
그리고, 상기 근 입력부(80)는, 코드 발생 다항식 g(x)의 근들(a0~a7)이 저장되어 있는 롬(82) 및, 상기 롬(82)에 저장되어 있는 코드 발생 다항식 g(x)의 근들(a0~a7)을 외부로부터 입력된 선택신호(mux_se1)에 따라 다중화시켜 출력하는 제1 다중화기(84)를 포함하여 구성되어 있다.The root input unit 80 includes a ROM 82 in which roots a 0 to a 7 of a code generation polynomial g (x) are stored, and a code generation polynomial g stored in the ROM 82. and a first multiplexer 84 to multiplex and output the roots a 0 to a 7 of x in accordance with the selection signal mux_se1 input from the outside.
상기와 같이 구성된 본 발명에 따른 리드 솔로몬 복호기의 신드롬 계산장치의 작용 및 효과를 상세히 설명하면 다음과 같다.Referring to the operation and effects of the syndrome calculation device of the Reed Solomon decoder according to the present invention configured as described above in detail as follows.
갈로아체 덧셈기(30)는 수신 심볼(ri)을 입력받아 상기 수신 심볼(ri)에 갈로아체 덧셈기(90)에서 출력된 중간값을 차례대로 더하여 중간값용 시프트 레지스터(40) 및 신드롬 선택부(50)로 각각 출력한다.Galois field adder 30 is received symbols (r i), the input receiving the received symbols (r i) in the Galois field adder 90, the intermediate value a turn in addition intermediate gapyong shift register 40 and the syndrome selector outputs in Output each to (50).
그리고, 상기 중간값용 시프트 레지스터(40)는 상기 갈로아체 덧셈기(30)에 서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 피드백 선택부(70)의 제2 다중화기(72)로 입력한다.The intermediate value shift register 40 shifts the value output from the Galois adder 30 according to the bit clock bit_clk and inputs it to the second multiplexer 72 of the feedback selector 70. .
이때, 상기 중간값용 시프트 레지스터(40)는 코드워드 중 마지막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)를 리셋단자(rst)로 입력받아 리셋한다.At this time, the intermediate shift register 40 receives and resets the first codeword end signal cw_end1 which becomes 1 while the last symbol r 0 of the codewords is input as the reset terminal rst.
그리고, 신드롬 선택부(50)의 논리합 게이트(52)는 코드워드중 마지막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)와 코드워드중 마지막에서 두 번째 심볼(r1)이 입력되는 동안에 1이 되는 제2 코드워드 종료신호(cw_end2)를 논리합하여 제1 다중화기(56)의 선택신호로 입력하고, 상기 제1다중화기(56)는 상기 논리합게이트(52)에서 출력된 신호를 선택신호로 입력받아 상기 선택신호에 따라 제1롬(54)에 저장되어 있는 0 또는 상기 갈로아체 덧셈기(30)에서 출력된 값을 선택적으로 신드롬용 시프트 레지스터(60)에 출력한다.In addition, the OR gate 52 of the syndrome selecting unit 50 includes a first codeword end signal cw_end1 which becomes 1 while the last symbol r 0 of the codeword is input and the second to last symbol of the codeword ( While r 1 ) is input, the second codeword end signal cw_end2, which is 1, is logically summed and input as a selection signal of the first multiplexer 56, and the first multiplexer 56 is configured to perform the logic sum gate 52. In response to the signal output from the input signal as a selection signal, 0 stored in the first ROM 54 or the value output from the galloche adder 30 is selectively stored in the syndrome shift register 60 according to the selection signal. Output
즉, 상기 제1다중화기(56)는 상기 선택신호가 1이면 상기 갈로아체 덧셈기(30)에서 출력된 값을 선택하여 신드롬용 시프트 레지스터(60)로 출력하고, 상기 선택신호가 0이면 상기 제1롬(54)에 저장되어 있는 0을 상기 신드롬용 시프트 레지스터(60)로 출력하는 것이다.That is, when the selection signal is 1, the first multiplexer 56 selects the value output from the galloche adder 30 and outputs it to the syndrome shift register 60, and when the selection signal is 0, the first multiplexer 56 selects the value. 0 stored in one ROM 54 is outputted to the syndrome shift register 60.
그리고, 신드롬용 시프트 레지스터(60)는 상기 신드롬 선택부(50)에서 출력된 값을 비트 클럭(bit_clk)에 따라 시프트시켜 출력한다.The syndrome shift register 60 shifts the value output from the syndrome selector 50 according to the bit clock bit_clk and outputs the shifted value.
또한, 피드백 선택부(70)는 코드 워드의 마지막 수신 심볼(r0)이 입력되는 기간이 아니면 상기 중간값용 시프트 레지스터(40)에서 출력된 값을 선택하여 출력하고, 코드 워드의 마지막 수신 심볼(r0)이 입력되는 기간에는 상기 신드롬용 시프트 레지스터(60)에서 출력된 값을 선택하여 상기 갈로아체 곱셈기(90)로 입력한다.In addition, the feedback selector 70 selects and outputs a value output from the shift register 40 for the intermediate value when the last received symbol r 0 of the code word is not input, and then outputs the last received symbol ( r 0 ) is input to the galloise multiplier 90 by selecting a value output from the syndrome shift register 60.
즉, 상기 피드백 선택부(70)의 제2다중화기(72)는 코드워드중 마지막심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1)를 선택신호로 입력받아 상기 제1 코드워드 종료신호(cw_end1)가 1이면 상기 신드롬용 시프트 레지스터(60)에서 출력된 값을 선택하여 상기 갈로아체 곱셈기(90)로 입력하고, 상기 제1 코드워드 종료신호(cw_end1)가 0이면 상기 중간값용 시프트 레지스터(40)에서 출력된 값을 선택하여 상기 갈로아체 곱셈기(30)로 입력하는 것이다.That is, the second multiplexer 72 of the feedback selector 70 receives the first codeword end signal cw_end1 which becomes 1 while the last symbol r 0 of the codewords is input as the selection signal. If the first codeword end signal cw_end1 is 1, a value output from the syndrome shift register 60 is selected and input to the galloche multiplier 90, and the first codeword end signal cw_end1 is 0. In this case, a value output from the intermediate shift register 40 is selected and inputted to the galloche multiplier 30.
그리고, 근 입력부(80)는 한 심볼 클럭 사이클 동안에 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 갈로아체 곱셈기(90)로 입력한다.The root input unit 80 sequentially inputs the roots a 0 to a 7 of the plurality of code generation polynomials g (x) to the Galloiche multiplier 90 during one symbol clock cycle.
즉, 상기 근 입력부(80)의 제3 다중화기는 제2롬(82)에 저장되어 있는 코드 발생 다항식 g(x)의 근(a0~a7)을 외부로부터 입력된 선택신호(mux_se1)에 따라 다중화시켜 상기 갈로아체 곱셈기(90)로 입력하는 것이다.That is, the third multiplexer of the root input unit 80 transfers the roots a 0 to a 7 of the code generation polynomial g (x) stored in the second ROM 82 to the selection signal mux_se1 input from the outside. Multiplexing is then input to the galloche multiplier 90.
그리고 , 상기 갈로아체 곱셈기(90)는 상기 피드백 선택부(70)에서 출력된값과 상기 근 입력부(80)에서 입력된 다수개의 코드 발생 다항식 g(x)의 근(a0~a7)을 차례대로 곱하여 중간값을 상기 갈로아체 덧셈기(30)로 입력한다.In addition, the galloise multiplier 90 may calculate the roots a 0 to a 7 of the values output from the feedback selector 70 and the plurality of code generation polynomials g (x) input from the root input unit 80. By multiplying them in turn, the median value is inputted into the galloche adder 30.
즉, 제6도에 도시된 바와 같이, 코드워드중 마지막 심볼(r0)이 입력되는 동안에 1이 되는 제1 코드워드 종료신호(cw_end1) 또는, 코드워드중 마지막에서 두 번째 심볼(r1)이 입력되는 동안에 1되는 제2 코드워드 종료신호(cw_end2)가 1일 때 상기 신드롬 시프트 레지스터(60)가 동작된다.That is, as illustrated in Figure 6, the code words of the last symbol (r 0) the second symbol from the last of the first codeword end signal (cw_end1) or the code word is 1, while the input (r 1) The syndrome shift register 60 is operated when the second codeword end signal cw_end2, which is 1 during inputting, is 1.
따라서, 제2 코드워드 종료신호(cw_end2)가 1일 동안에 상기 중간값용 시프트 레지스터(40)에 저장되어 있는 값을 로딩(loading)할 수 있는 것이다.Accordingly, the second codeword end signal cw_end2 may load a value stored in the intermediate shift register 40 for one day.
그리고, 제2 코드워드 종료신호(cw_end2)가 1일 때 갈로아체 곱셈기(90)로 입력되는 값은 상기 신드롬용 시프트 레지스터(60)에서 출력된 값이므로, 수신 심볼(r1)과 더해지는 값은 상기 신드롬용 시프트 레지스터(60)에 저장된 값이다.In addition, when the second codeword end signal cw_end2 is 1, the value input to the galloise multiplier 90 is a value output from the syndrome shift register 60, and thus a value added to the reception symbol r 1 is The value is stored in the syndrome shift register 60.
그리고, 상기 신드롬용 시프트 레지스터(60)에 저장된 값이 갈로아체 곱셈기(90) 및 갈로아체 덧셈기(30)를 통해 계산된 값은 다시 신드롬용 시프트 레지스터(60)에 다시 저장되므로, 계산이 끝난 신드롬(synd)은 상기 신드롬용 시프트 레지스터(60)에 저장되었다가 출력되는 것이다.In addition, since the value stored in the syndrome shift register 60 is calculated by the galloa multiplier 90 and the galloa adder 30, the value is stored again in the syndrome shift register 60, and thus the calculated syndrome is completed. Synd is stored in the syndrome shift register 60 and then output.
상기와 같이 동작하는 본 발명은, 심볼 클럭의 8배 빠르기인 사이클이 16.67nsec의 비트 클럭을 이용하여 8개의 신드롬을 동시에 계산함으로써 대기시간을 대폭 줄일 수 있을 뿐만 아니라 신드롬 계산장치 전체에 필요한 신드롬 계산셀을 1/8로 줄일 수 있는 것이다.According to the present invention operating as described above, a cycle that is eight times faster than a symbol clock can simultaneously calculate eight syndromes using a bit clock of 16.67 nsec, thereby greatly reducing the waiting time and calculating a syndrome required for the entire syndrome calculation apparatus. The cell can be reduced to 1 / 8th.
예를 들어, 리드 솔로몬 코드(204, 188) 에서는 종래의 경우에 16개의 신드롬 계산셀이 필요하였으나, 본 발명에 따른 신드롬 계산셀을 사용하면 2개로 줄일 수 있다.For example, in the conventional Reed Solomon codes 204 and 188, 16 syndrome calculation cells are required. However, by using the syndrome calculation cells according to the present invention, the number can be reduced to two.
따라서, 갈로아체 덧셈기와 갈로아체 곱셈기를 1/8로 줄일 수 있는 것이다.Thus, the Galoache adder and the Galoache multiplier can be reduced to 1 / 8th.
상기와 같은 본 발명의 실시예에서는 1심볼 클럭 사이클이 8 비트 클럭 사이클로 되는 비트 클럭을 이용하여 한 개의 신드롬 계산셀에서 8개의 신드롬(예컨데, S0~S7)을 계산하여 출력하는 구성에 대해서만 설명 및 도시화되어 있으나, 본 발명은 이에 한정되지 않고 1심볼 클럭의 사이클에 대해 2개 이상 비트 클럭 사이클 개수로 사용하기만 하면 된다.In the embodiment of the present invention as described above, only the configuration for calculating and outputting eight syndromes (for example, S 0 to S 7 ) in one syndrome calculation cell using a bit clock in which one symbol clock cycle becomes an eight-bit clock cycle Although described and illustrated, the present invention is not limited thereto, and the present invention need only be used as the number of two or more bit clock cycles per cycle of one symbol clock.
예를 들어, 1심볼 클럭 사이클이 16비트 클럭 사이클로 되는 경우에는 제5도의 롬(42)에는 16개의 롬이 필요함과 더불어 레지스터부(64)의 레지스터가 16개 필요하게 되고, 1심볼 클럭 사이클이 36비트 클럭 사이클로 되는 경우에 제5도의 롬(42)에는 32개의 롬이 필요함과 더불어 레지스터부(64)의 레지스터가 32개 필요하게 되는 것이다.For example, when one symbol clock cycle becomes a 16-bit clock cycle, the ROM 42 of FIG. 5 requires 16 ROMs, and 16 registers of the register unit 64 require one symbol clock cycle. In the case of 36-bit clock cycles, the ROM 42 of FIG. 5 requires 32 ROMs and 32 registers of the register unit 64.
상기와 같이, 1심볼 클럭 사이클이 16비트 클럭 사이클이 되는 경우에는 필요한 신드롬 계산셀이(2t-1)/16개가 되고, 1심볼 클럭 사이클이 32비트 클럭 사이클이 되는 경우에는 필요한 신드롬 계산셀이(2t-1)/32개가 되는 것이다.As described above, when one symbol clock cycle becomes a 16-bit clock cycle, the required syndrome calculation cells become (2t-1) / 16, and when one symbol clock cycle becomes a 32-bit clock cycle, the required syndrome calculation cells become (2t-1) / 32.
이때, 상기와 같이 신드롬 계산셀의 신드롬 계산 능력을 확장시키기 위해서는 갈로아체 곱셈기의 연산 속도가 상기 조건을 만족시킬수 있으면 된다.In this case, in order to expand the syndrome calculation capability of the syndrome calculation cell, the computational speed of the galloise multiplier may satisfy the above condition.
따라서, 상기 1심볼 클럭 사이클에 해당하는 비트 클럭 사이클의 개수는 상기와 같은 갈로아체 곱셈기의 연산 속도를 만족시키면서 수신신호 r(x)에 따라 최적의 개수로 설계하면 된다.Accordingly, the number of bit clock cycles corresponding to the one symbol clock cycle may be designed to an optimal number according to the reception signal r (x) while satisfying the operation speed of the galloise multiplier.
이상에서 살펴본 바와 같이, 본 발명에 따르면 신드롬을 계산하는 과정에서 생기는 중간값을 저장하기 위한 시프트 레지스터와 최종적으로 출력할 신드롬값을 저장하기 위한 시프트 레지스터를 구분하여 사용하므로써 신드롬 계산셀을 비트 클럭에 의해 동작되도록 구현함으로써 그 구조가 간단한 효과가 있다.As described above, according to the present invention, by using a shift register for storing the intermediate value generated during the calculation of the syndrome and a shift register for storing the finally outputted syndrome value, the syndrome calculation cell is assigned to the bit clock. By implementing to operate by the structure has a simple effect.
Claims (5)
Priority Applications (5)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
KR1019960005446A KR100212829B1 (en) | 1996-02-29 | 1996-02-29 | Syndrome Calculator of Reed Solomon Decoder |
US08/755,580 US5805617A (en) | 1996-02-28 | 1996-11-25 | Apparatus for computing error correction syndromes |
EP96308523A EP0793351A1 (en) | 1996-02-28 | 1996-11-26 | Apparatus for computing error correction syndromes |
CN96120992A CN1158519A (en) | 1996-02-28 | 1996-12-03 | Apparatus for computing error correction syndromes |
JP8324097A JPH09247000A (en) | 1996-02-28 | 1996-12-04 | Syndrome calculating device for error correction |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
KR1019960005446A KR100212829B1 (en) | 1996-02-29 | 1996-02-29 | Syndrome Calculator of Reed Solomon Decoder |
Publications (2)
Publication Number | Publication Date |
---|---|
KR970063959A KR970063959A (en) | 1997-09-12 |
KR100212829B1 true KR100212829B1 (en) | 1999-08-02 |
Family
ID=19452305
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
KR1019960005446A Expired - Fee Related KR100212829B1 (en) | 1996-02-28 | 1996-02-29 | Syndrome Calculator of Reed Solomon Decoder |
Country Status (1)
Country | Link |
---|---|
KR (1) | KR100212829B1 (en) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US9467174B2 (en) | 2014-03-14 | 2016-10-11 | Samsung Electronics Co., Ltd. | Low complexity high-order syndrome calculator for block codes and method of calculating high-order syndrome |
-
1996
- 1996-02-29 KR KR1019960005446A patent/KR100212829B1/en not_active Expired - Fee Related
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US9467174B2 (en) | 2014-03-14 | 2016-10-11 | Samsung Electronics Co., Ltd. | Low complexity high-order syndrome calculator for block codes and method of calculating high-order syndrome |
Also Published As
Publication number | Publication date |
---|---|
KR970063959A (en) | 1997-09-12 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US4649541A (en) | Reed-Solomon decoder | |
EP0147041B1 (en) | Error protection apparatus | |
US4782490A (en) | Method and a system for multiple error detection and correction | |
US7028247B2 (en) | Error correction code circuit with reduced hardware complexity | |
KR100192795B1 (en) | Error Position Polynomial Computation Device for Reed Solomon Decoder | |
US5805617A (en) | Apparatus for computing error correction syndromes | |
KR20040075954A (en) | Dual chien search blocks in an error-correcting decoder | |
US5936978A (en) | Shortened fire code error-trapping decoding method and apparatus | |
JP3305525B2 (en) | Decoder, error locator sequence generator and decoding method | |
EP1102406A2 (en) | Apparatus and method for decoding digital data | |
US6263471B1 (en) | Method and apparatus for decoding an error correction code | |
KR100212829B1 (en) | Syndrome Calculator of Reed Solomon Decoder | |
JP3454962B2 (en) | Error correction code encoder and decoder | |
KR100212825B1 (en) | Syndrome calculating apparatus of reed solomon decoder | |
KR100212830B1 (en) | Syndrome Calculator of Reed Solomon Decoder | |
EP0793352B1 (en) | Apparatus for determining the error evaluator polynomial for use in a Reed-Solomon decoder | |
KR100212828B1 (en) | Syndrome calculating apparatus of reed solomon decoder | |
KR100212826B1 (en) | Syndrome calculating apparatus of reed solomon decoder | |
KR100195739B1 (en) | Error Position Polynomial Evaluation Device of Reed Solomon Decoder | |
KR100747487B1 (en) | Reed-Solomon decoder and circuits of the modified Euclid's algorithm | |
KR100192790B1 (en) | Device for calculating coefficient of error-evaluator polynominal in a rs decoder | |
KR100191248B1 (en) | Reed solomon coder | |
KR100192788B1 (en) | Device for calculating coefficient of error-evaluator polynominal in a rs decoder | |
KR100192802B1 (en) | Error value calculation and correction device of Reed Solomon decoder | |
KR100202949B1 (en) | Error corrector of reed-solomon decoder |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A201 | Request for examination | ||
PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 19960229 |
|
PA0201 | Request for examination |
Patent event code: PA02012R01D Patent event date: 19960229 Comment text: Request for Examination of Application |
|
PG1501 | Laying open of application | ||
E902 | Notification of reason for refusal | ||
PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 19981027 Patent event code: PE09021S01D |
|
E701 | Decision to grant or registration of patent right | ||
PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 19990223 |
|
GRNT | Written decision to grant | ||
PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 19990512 Patent event code: PR07011E01D |
|
PR1002 | Payment of registration fee |
Payment date: 19990513 End annual number: 3 Start annual number: 1 |
|
PG1601 | Publication of registration | ||
LAPS | Lapse due to unpaid annual fee | ||
PC1903 | Unpaid annual fee |
Termination category: Default of registration fee Termination date: 20030210 |