• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    PURPOSE: A new pipeline Reed-Solomon decoding algorithms is provided to maximize hardware efficiency by modifying a modified Euclid's algorithm. CONSTITUTION: According to the decoding method of a reed solomon decoder outputting modified data code polynomial by performing calculating to correct an error of a received data code from a received data code polynomial and a received eraser, the data code and the erase to be corrected by the reed solomon decoder are received(S610). The first Chien search is performed in the first sub stage, by the reed solomon decoder. The second modified syndrome polynomial and the second eraser locator polynomial are calculated in the first sub stage, by the reed solomon decoder. The second errata locator polynomial and the second errata value polynomial are calculated from a modified Euclid's algorithm calculation modified in the second sub stage, by the reed solomon decoder(S635). And the third syndrome polynomial is calculated among the first sub stage and the second sub stage, by the reed solomon decoder.
    公开号:KR20040050536A
    申请号:KR1020020078389
    申请日:2002-12-10
    公开日:2004-06-16
    发明作者:이수웅；김대웅
    申请人:삼성전자주식회사；
    IPC主号:
    专利说明:

    New pipline Reed Solomon decoding method for providing extreme hardware efficiency
    [8] The present invention relates to a Reed Solomon decoding method, and more particularly to a Reed Solomon decoding method using a modified Euclid's algorithm.
    [9] In a general digital communication or storage system, an error correction code system that detects an error occurring during data transmission or decoding and adds an RS (Reed Solomon) code to the transmission data to correct the error. That is, the RS code is a symbol that can detect the location of an error and its error value during decoding of received data, that is, a code for error control in units of bits. An error is represented by an erasure that specifies the location of the error and its error value, and the error and the error value are called an errorta.
    [10] First, an encoding and decoding algorithm of an RS code will be described based on the (n, k, d) RS code generated in the Galois field GF (2 m ). n is the code length, k is the information length, and d is the minimum distance.
    [11] In this case, it is assumed that the data code to be transmitted, that is, the information polynomial D (x) is equal to [Equation 1].
    [12]
    [13] At this time, the sum of D (x) x d-1 divided by the generator polynomial G (x) to be the parity polynomial P (x) is added, and the actual code polynomial C to be transmitted is added. (x) is generated as shown in [Equation 2].
    [14]
    [15] Eventually, the code polynomial C (x) is divided into generator polynomial G (x), and based on this, when decoding at the receiving end, a syndrome is generated to generate an error polynomial ( error polynomial).
    [16] The error caused in the transmission channel is intervened in the form of an error polynomial E (x) as shown in [Equation 3], and a distortion as shown in [Equation 4] occurs in R (x), which is a polynomial of the received data code.
    [17]
    [18]
    [19] Therefore, finding E '(x) equal to E (x) at the receiving end can completely recover the corrected code polynomial C (x).
    [20] 1 is a block diagram of a Reed Solomon decoder using a conventional modified Euclid's algorithm.
    [21] Referring to FIG. 1, a Reed Solomon decoder using a conventional modified Euclid's algorithm includes a syndrome polynomial calculation unit 110, a modified syndrome polynomial calculation unit 120, and a seventh generation Edge locator polynomial calculation unit 130, modified Euclid's algorithm calculation unit 140, Chien search unit 150, delay buffer unit 160, And an error correction unit 170.
    [22] The syndrome polynomial calculation unit 110 calculates a syndrome polynomial S (x) from R (x), which is a received data code polynomial, as shown in [Equation 5].
    [23]
    [24] Here, the minimum distance d = n-k + 1, and since the coefficient of the syndrome polynomial S (x) is (d-1), the number of unknowns must be within (d-1) E '(x) Can be solved. In the case of an error, the unknown number is the position of the error and two error values, and in the case of the eraser, since the unknown number is one error value, {2 × (number of errors) + (number of erasers)} ≤ (d-1) The correct E '(x) can be found in.
    [25] FIG. 2 is a circuit diagram of the syndrome polynomial calculator 110 of FIG. 1.
    [26] Referring to FIG. 2, the syndrome polynomial calculator 110 adds and multiplies the S (x) calculation register values S 0, i to S d-2, i from the received data code r i . By repeating to calculate a polynomial such as [Equation 6] to calculate the syndrome polynomial S (x) that satisfies [Equation 5]. Here, if n r i values are input without interruption, they are performed only in n cycles of the clock.
    [27]
    [28] The modified syndrome polynomial calculation unit 120 calculates the modified syndrome polynomial T (x) from the input syndrome polynomial S (x), as shown in [Equation 7]. Calculate
    [29]
    [30] The erasure locator polynomial calculation unit 130 calculates the erasure locator polynomial Λ (x) from the input erasure as shown in [Equation 8].
    [31]
    [32] FIG. 3 is a circuit diagram of the modified syndrome polynomial calculation unit 120 or the erasure locator polynomial calculation unit 130 of FIG. 1.
    [33] Referring to FIG. 3, the modified syndrome polynomial calculation unit 120 or the erasure locator polynomial calculation unit 130 may calculate T (x), or Λ from α -i calculated above. (x) Repeat the addition and multiplication of the calculation register values (Λ 0, i ~ Λ d-2, i ) to calculate a polynomial such as [Equation 9] or [Equation 10], and [Equation 7] Calculate the modified syndrome polynomial T (x) and the erasure locator polynomial Λ (x) that satisfies [Equation 8].
    [34] Here, the circuitry for calculating the modified syndrome polynomial T (x) and erasure locator polynomial Λ (x), proceeds simultaneously with separate hardware and differs only in initial values. Also, if n erasure values are input without interrupts, such values are performed only in n periods of the clock. However, in FIG. 3, if α -i ∈Λ, ENABLE = 1, otherwise ENABLE = 0.
    [35]
    [36]
    [37] As shown in [Equation 9], the modified syndrome polynomial T (x) is initialized to the syndrome polynomial S (x) calculated above without setting the initial value to 1. Also, to perform modx d-1 , cancel the x d-1 order term. parts of generating α -i can be shared with α -i generation part for generating a erasure location polynomial (erasure locator polynomial) Λ (x ).
    [38] The modified Euclid's algorithm calculation unit 140 is the most important process for solving an equation having an unknown value and a position of an error, and takes the largest part in an algorithm or hardware.
    [39] That is, an errata locator polynomial, such as Equation 12, which repeats to satisfy Equation 11 to be deg (λ i (x))> deg (R i (x)). Calculate σ (x) and the errata evaluator polynomial ω (x).
    [40]
    [41]
    [42] At this time, R (x), Q (x), λ (x), μ (x) calculation registers, multipliers, and summers are needed to calculate Equation (11).
    [43] The Chien search unit 150 may be calculated from Equation 13 and errata locator polynomial σ (x) and errata evaluator polynomial ω (x) calculated above. Equation 14 Calculates the error rudder position and error rudder value satisfying each of them.
    [44]
    [45]
    [46] 4 is a circuit diagram of an error rudder position (i) calculator of the Chien search unit 160 of FIG. 1. FIG. 5 is a circuit diagram of an error value e i calculator of the Chien search unit 160 of FIG. 1.
    [47] Referring to FIGS. 4 and 5, the Chien search unit 160 simultaneously calculates the error rudder position i and the error rudder value e i without receiving an external input and simultaneously calculates the data with separate hardware. The calculation is completed exactly in n cycles of the clock.
    [48] The circuit of FIG. 4 calculates [Equation 15], and the circuit of FIG. 5 is necessary to calculate [Equation 16].
    [49]
    [50]
    [51] From the calculated e i , the error polynomial E '(x) becomes as shown in [Equation 17].
    [52]
    [53] The delay buffer unit 160 may receive the received data code polynomial R () such that the error corrected data code polynomial C (x) is calculated in the error correction unit 170 as shown in Equation 18. delay x).
    [54]
    [55] However, the Reed-Solomon decoding method of the pipeline structure using the conventional modified Euclid's algorithm as described above, four stage form, that is, syndrome polynomial S (x) calculation, erasure position polynomial (erasure) locator polynomial) Λ (x) calculation, modified syndrome polynomial T (x) calculation, and Chien search calculation operation are performed sequentially, and all four of these calculations are performed within one stage. Is in a state. Therefore, when calculating the modified Euclid's algorithm, since all other hardware blocks are also in operation, all operations are overlapped in timing so that hardware resource sharing cannot be performed at all. Accordingly, in order to calculate the modified Euclid's algorithm, separate hardware, that is, registers, multipliers, and adders must be provided, thereby increasing the decoder chip size.
    [56] Accordingly, the technical problem to be achieved by the present invention is a modified Euclidean algorithm (modified syndrome polynomial T (x), erasure locator polynomial Λ (x), circuits for calculating the Chien search In order to be shared with circuits for calculating Euclid's algorithm, the present invention provides a new pipelined Reed Solomon decoding method modified from a modified Euclid's algorithm.
    [1] BRIEF DESCRIPTION OF THE DRAWINGS In order to better understand the drawings cited in the detailed description of the invention, a brief description of each drawing is provided.
    [2] 1 is a block diagram of a Reed Solomon decoder using a conventional modified Euclid's algorithm.
    [3] FIG. 2 is a circuit diagram of a syndrome polynomial calculation unit of FIG. 1.
    [4] FIG. 3 is a circuit diagram of an erasure locator polynomial calculation unit or a modified syndrome polynomial calculation unit of FIG. 1.
    [5] 4 is a circuit diagram of an error locator polynomial calculator of the Chien search unit of FIG. 1.
    [6] FIG. 5 is a circuit diagram of an errata evaluator polynomial calculator of the Chien search unit of FIG. 1.
    [7] 6 is a flowchart illustrating a Reed Solomon decoding method of a new pipeline structure according to the present invention.
    [57] According to another aspect of the present invention, there is provided a reed solo decoding method of a pipeline structure according to the present invention, wherein a corrected data code polynomial is obtained by calculating a correction of an error of the received data code from a received data code polynomial and a received eraser. In the decoding method of an output Reed Solomon decoder, the following steps are provided.
    [58] That is, the Reed Solomon decoding method of the new pipeline structure according to the present invention includes: receiving the data code and the eraser to be corrected by the Reed Solomon decoder; Performing, by the Reed Solomon decoder, a first search in a first sub-stage; Calculating, by the Reed Solomon decoder, a second modified syndrome polynomial and a second erasure position polynomial at the first sub-stage; Calculating, by the Reed Solomon decoder, a second error position polynomial and a second error value polynomial from the modified Euclidean algorithm calculation at the second sub-stage; And performing, by the Reed Solomon decoder, a third syndrome polynomial calculation during the first sub stage and the second sub stage.
    [59] In this case, the first search is performed by performing a first error polynomial, a first modified syndrome polynomial, and a first error location polynomial and a first error value extracted from the first erasure position polynomial. It is characterized by being performed by a polynomial.
    [60] The calculation of each of the second modified syndrome polynomial and the second eraser position polynomial is performed by the second syndrome polynomial calculated at the previous stage and the eraser received at the previous stage.
    [61] The modified modified Euclidean algorithm is calculated by
    [62]
    [63]
    [64] It is characterized in that performed by.
    [65] The calculation of each of the second error position polynomial and the second error value polynomial was used when calculating the first search and the second modified syndrome polynomial and the second erasure position polynomial in the first sub-stage. It is characterized by using a predetermined hardware sharing.
    [66] The predetermined hardware is hardware used for multiplication and summation with a first-value search calculation register, a second modification syndrome polynomial calculation register, and the second erasure position polynomial calculation register.
    [67] In order to fully understand the present invention, the operational advantages of the present invention, and the objects achieved by the practice of the present invention, reference should be made to the accompanying drawings which illustrate preferred embodiments of the present invention and the contents described in the accompanying drawings.
    [68] Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Like reference numerals in the drawings denote like elements.
    [69] 6 is a flowchart illustrating a Reed Solomon decoding method of a new pipeline structure according to the present invention.
    [70] Referring to FIG. 6, the Reed-Solomon decoding method of the new pipeline structure according to the present invention includes a data code corrected by calculating a correction for an error of the received data code from a received data code polynomial R (x) and a received eraser. A decoding method of a Reed Solomon decoder that outputs a polynomial C (x), which is performed with the following new pipeline structure.
    [71] First, a data code r i and an eraser to be corrected outside the decoder are received (S610).
    [72] [Table 1] is a table for explaining the Reed Solomon decoding stage of the new pipeline structure according to the present invention.
    [73] TABLE 1
    [74]
    [75] Referring to [Table 1], the first syndrome polynomial S (x) to the third syndrome polynomial S (x) in a pipeline structure at each stage of stage 0 to stage 2 are shown. Is calculated (S620). Here, the first syndrome polynomial S (x) is calculated in "Syndrome polynomial calculation 0" in Table 1, and the second syndrome polynomial S (x) is calculated in "Syndrome polynomial calculation 1". In the "Syndrome Polynomial Calculation 2", the Chien search, the modified syndrome polynomial T (x) calculation, the seventh order, as the third syndrome polynomial S (x) is calculated In the calculation of the positioner locator polynomial Λ (x), similarly, "0", "1", and "2" representing stages, "first", "second", representing different calculation values, And "third".
    [76] In " Stage 1 " (S630), the first modified syndrome polynomial T (x) and the first eraser position in one sub-stage while the second syndrome polynomial S (x) is calculated The erasure locator polynomial Λ (x) is calculated (S633) and the first errata locator polynomial σ (x) and the second from the modified Euclid's algorithm calculation at another substage. 1 error value polynomial (errata evaluator polynomial) ω (x) is calculated (S635).
    [77] As a result, when all the hardware of the decoder becomes "stage 2", Reed Solomon decoding of the new pipeline structure according to the present invention is performed as follows.
    [78] Referring to [Table 1], the first sub stage performs a chien search. In addition, a second modified syndrome polynomial T (x) and a second erasure locator polynomial Λ (x) calculation are simultaneously performed in the first sub-stage.
    [79] Here, the performance of the first chien search may include: first syndrome polynomial S (x), first modified syndrome polynomial T (x), and The first errata locator polynomial σ (x) extracted from the erasure locator polynomial Λ (x) and the first errata evaluator polynomial ω (x) Is performed. In addition, the calculation of each of the second modified syndrome polynomial T (x) and the second erasure locator polynomial Λ (x) is calculated from the second syndrome polynomial calculated in the previous stage. ) By S (x) and the eraser received at the previous stage.
    [80] In the second sub-stage, the second errata locator polynomial σ (x) and second errata evaluator polynomial ω (x) calculations are calculated from the modified Euclid's algorithm calculation. (S640). In the first sub-stage and the second sub-stage, a third syndrome polynomial S (x) is simultaneously calculated (S620). Here, the modified Euclid's algorithm calculation is a new algorithm modified from the conventional modified Euclid's algorithm, and is modified as shown in Equation 19.
    [81] Here, the calculation of each of the second errata locator polynomial σ (x) and the second errata evaluator polynomial ω (x) calculated by the algorithm shown in Equation 19 is When calculating the first Chien search and the second modified syndrome polynomial T (x) and the second erasure locator polynomial Λ (x) in the first sub-stage, Share any hardware that was used. That is, a first Chien search calculation register, the second modified syndrome polynomial T (x) calculation register, and the second erasure locator polynomial Λ (x) calculation register And other hardware used for multiplication and summation.
    [82]
    [83]
    [84] In more detail, when the conventional modified Euclidean algorithm is modified as shown in Equation 19, the multiplier, which is 4d, is reduced to 2d, and the divider is increased by one. In Equation 19, the process of calculating R i (x) and λ i (x) multiplies (d i-1 ) by each of the polynomials L1 i-1 (x) and L2 i-1 (x) Another polynomial S1 i-1 (x) and S2 i-1 (x) is shifted (x li-1 ) and adds the equation. This is equivalent to Equation 10, which computes the erasure locator polynomial Λ (x) or the modified syndrome polynomial T (x). It is possible to share the erasure locator polynomial Λ (x), and the modified syndrome polynomial T (x) calculation registers. In the same manner, it is possible to share the Chien search calculation register for calculating the error rudder position i and the error rudder value ei in the modified algorithm calculation of Equation 19. In addition, a divider added for calculating (d i-1 ) may use a divider used in a Cheen search. That is, the modified algorithm of Equation 19 requires four registers of (d-1) m-bits, which can be calculated by sharing hardware as described above.
    [85] Table 2 shows an example of hardware shared when calculating a modified Euclid's algorithm of Equation 19 in the new pipelined Reed Solomon decoding method according to the present invention.
    [86] That is, as shown in Table 2, each of the Q i (x), μ i (x), λ i (x), and R i (x) calculation registers is represented by T (x), Λ (x), σ ( x) and ω (x) calculation registers. The share of hardware for the remaining multiplication or sum is also shown in [Table 2]. Doing so, when starting the modified Euclid's algorithm of Equation 19, initializing the Q i (x), μ i (x) calculations and starting the search on the values, σ (x), ω (x) initialization is not necessary. Therefore, if only MUX is added properly, almost all of the hardware becomes a shareable pipeline structure.
    [87] TABLE 2
    [88]
    [89] In Equation 19, a circuit for determining deg (R i ), deg (Q i ), and deg (λ i ) and the x li-1 shift operation can be implemented by a combinational logic circuit, which requires a separate clock delay. I never do that. Thus, one clock delay is needed to calculate the four i-th to i-th polynomials, i.e., Q i (x), μ i (x), λ i (x), and R i (x). Therefore, the maximum (d-1) clock is required to perform the entire algorithm (Equation 19).
    [90] The error polynomial E '(x) is extracted from the errata locator polynomial σ (x) and the errata evaluator polynomial ω (x) sequentially calculated as described above (S650). ), The error polynomial E '(x) is subjected to error correction by calculation with the delayed received data code polynomial R (x) during the above calculation (S660), and the corrected data code polynomial C (x) is output (S670).
    [91] As described above, the timing relationship for the Reed Solomon decoding method of the new pipeline structure according to the present invention will be described in more detail.
    [92] As described above, hardware that performs erasure locator polynomial Λ (x), modified syndrome polynomial T (x), and Chien search calculations may be modified with modified [ When performing the modified Euclid's algorithm calculation of Equation 19, the possibility of being fully shared was suggested. Thus, when performing calculations with this new pipeline structure, the modified Euclid's algorithm calculation of Equation (19), which is the most expensive, unless otherwise overlapped in timing, is performed on other hardware as described above. This can be done by sharing resources with the block, which can greatly reduce the chip size of the decoder.
    [93] That is, the conventional decoder has four stage forms, namely, a syndrome polynomial S (x) calculation, an erasure locator polynomial Λ (x) calculation, a modified syndrome polynomial T ( x) Calculation and Chien search calculation operations are performed sequentially, and all four of these calculations are in operation in one stage. Therefore, in the conventional decoder, when calculating the modified Euclid's algorithm, all other hardware blocks are also in operation state, and thus all operations are overlapped in timing so that resource sharing cannot be performed at all. However, in the Reed Solomon decoding method of the new pipeline structure according to the present invention, when calculating the modified Euclid's algorithm of Equation [19], as shown in "Stage 2" of [Table 1], Since the hardware that performs the erasure locator polynomial Λ (x), the modified syndrome polynomial T (x), and the Chien search calculation has ended the previous operation, There is no overlap.
    [94] In other words, as shown in Table 1, an erasure position locator in the form of a sub-stage without separating the performance of the modified Euclid's algorithm of Equation 19 into one stage. polynomial) Λ (x), glued together to the stage of calculating the modified syndrome polynomial T (x). Since the Chien search is performed on its own without any input, the calculation of the syndrome polynomial S (x) or modified syndrome polynomial T (x) and erasure that requires data entry is required. Terminate earlier than the position locator polynomial Λ (x) calculation. In this case, at the time of performing the modified Euclid's algorithm calculation of Equation 19, nothing except the syndrome polynomial S (x) calculation is performed at the same time. Thus, the resources used to calculate the erasure locator polynomial Λ (x), modified syndrome polynomial T (x), and chien search can be shared.
    [95] On the other hand, as shown in Table 1, the Reed Solomon decoding method of the new pipeline structure according to the present invention has one stage smaller than the pipeline stage (four stages) of the conventional decoder, but at a calculation speed or throughput. No damage occurs.
    [96] That is, a maximum (d-1) clock delay is required to perform the modified Euclid's algorithm calculation in Equation 19, while the remaining functions require a much larger n clock delay than this. . Thus, the number of clock delays needed for one stage only increases from n to (n + d-1).
    [97] In addition, data input required for conventional syndrome polynomial S (x) calculations is often performed in a separate memory. In the case of DRAM, several clock delays are required for one access. Due to the memory priority problem, the n clock delay or more is often required. Thus, in the Reed Solomon decoding method of the new pipeline structure according to the present invention, there is no loss of throughput.
    [98] In addition, the Reed Solomon decoding method of the new pipeline structure according to the present invention has one stage less than that of the conventional decoding method, thereby reducing the latency. There is a total 4 (n + α) clock delay in the case of the conventional decoding method, and a total 3 (n + d-1 + α) clock delay in the case of the Reed Solomon decoding method of the new pipeline structure according to the present invention. . At this time, since n is much larger than (d-1) in actual decoding processing, the latency is reduced by the {n-3 (d-1) + α} clock delay.
    [99] [Table 3] is a table comparing the decoder area and the conventional decoder area when using the Reed Solomon decoding method of the new pipeline structure according to the present invention by using hardware such as registers.
    [100] Referring to [Table 3], the actual area comparison was synthesized the operation defined in the Galois field GF ( 28 ), and weighted according to the relative number of gates. In Table 3, the hardware required to perform the modified Euclid's algorithm calculation of Equation 19 is indicated by parentheses (), and this part is in the new pipeline structure according to the present invention. It becomes a part to be shared. At this time, as shown in the total size of [Table 1], there is an overall reduction of more than 50%.
    [101] The new pipeline structure according to the present invention was actually applied to the digital processing part of the digital video disc (DVD) system, that is, the front-end processor design, and verified as a flat pin grid array (FPGA) chip. In the case of a DVD, the RS codes PI (182, 172, 11) and PO (208, 192, 17) defined in the Galois field GF (2 8 ) are applied, where the number of gates required for the calculation is 55,000. 50% reduction from gate to 28,000 gates.
    [102] TABLE 3
    [103]
    [104] As described above, the Reed Solomon decoding method of the new pipeline structure according to the present invention outputs a corrected data code polynomial by performing calculation to correct an error of the received data code from a received data code polynomial and a received eraser. In the decoding method of the Reed Solomon decoder, first, the data code to be corrected and the eraser are received. Extract the next necessary polynomials from the data code to be corrected and the eraser, perform a first Chien search at the first sub-stage and a modified syndrome polynomial T (x) and A second erase locator polynomial Λ (x) is calculated. In the second sub-stage, the second errata locator polynomial σ (x) and the second errata value polynomial (errata evaluator polynomial) from the modified Euclid's algorithm of Equation 19 ω (x) is calculated. In the first sub-stage and the second sub-stage, a third syndrome polynomial S (x) is simultaneously calculated.
    [105] As described above, optimal embodiments have been disclosed in the drawings and the specification. Although specific terms have been used herein, they are used only for the purpose of describing the present invention and are not intended to limit the scope of the invention as defined in the claims or the claims. Therefore, those skilled in the art will understand that various modifications and equivalent other embodiments are possible from this. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.
    [106] As described above, in the new pipeline Reed Solomon decoding method according to the present invention, a modified Euclid's algorithm calculation method is newly modified to modify the modified syndrome polynomial T (x), an erasure position. Circuits for calculating the erasure locator polynomial Λ (x), and Chien search may be shared with circuits for calculating the modified Euclid's algorithm. Therefore, the pipeline stage can be adjusted so that the above hardware cannot be overlapped in time to be shared with each other, so that the area can be reduced by 50% without the loss of throughput compared to the conventional decoder. Etc., hardware efficiency is maximized, and computational latency is reduced.
    权利要求:
    Claims (6)
    [1" claim-type="Currently amended] A decoding method of a Reed Solomon decoder which calculates an error of the received data code from a received data code polynomial and a received eraser and outputs a corrected data code polynomial.
    Receiving the data code and the eraser to correct by the Reed Solomon decoder;
    Performing, by the Reed Solomon decoder, a first search in a first sub-stage;
    Calculating, by the Reed Solomon decoder, a second modified syndrome polynomial and a second erasure position polynomial at the first sub-stage;
    Calculating, by the Reed Solomon decoder, a second error position polynomial and a second error value polynomial from the modified Euclidean algorithm calculation at the second sub-stage; And
    And performing, by the Reed Solomon decoder, a third syndrome polynomial calculation during the first and second sub-stages.
    [2" claim-type="Currently amended] The method of claim 1, wherein the first search is performed by:
    A new pipe characterized by being performed by a first syndrome polynomial, a first modified syndrome polynomial, and a first error position polynomial and a first error value polynomial extracted from the first erasure position polynomial Reed Solomon decoding method of line structure.
    [3" claim-type="Currently amended] The method of claim 1, wherein each of the second modified syndrome polynomial and the second erasure position polynomial is:
    And a second syndrome polynomial calculated at the previous stage and the eraser received at the previous stage.
    [4" claim-type="Currently amended] The method of claim 1, wherein the modified modified Euclidean algorithm calculation,
    Equation,


    Reed Solomon decoding method of a new pipeline structure, characterized in that performed by.
    [5" claim-type="Currently amended] The method of claim 1, wherein each of the second error position polynomial and the second error value polynomial is:
    In the first sub-stage, the first solo search and the second modified syndrome polynomial and the second eraser position polynomial are used to share predetermined hardware used for the new pipeline structure. Decoding method.
    [6" claim-type="Currently amended] The method of claim 5, wherein the predetermined hardware,
    And a hardware used for multiplication and summing with a first-value search calculation register, a second modification syndrome polynomial calculation register, and the second erasure position polynomial calculation register.
    类似技术:
    公开号 | 公开日 | 专利标题
    US8527850B1|2013-09-03|Architecture and control of reed-solomon error identification and evaluation
    Chen et al.2008|Error correction for multi-level NAND flash memory using Reed-Solomon codes
    US6637002B1|2003-10-21|Decoder for error correcting block codes
    Lee2003|High-speed VLSI architecture for parallel Reed-Solomon decoder
    US6219815B1|2001-04-17|High-speed syndrome calculation
    US6694476B1|2004-02-17|Reed-solomon encoder and decoder
    Choi et al.2009|VLSI implementation of BCH error correction for multilevel cell NAND flash memory
    US8122328B2|2012-02-21|Bose-Chaudhuri-Hocquenghem error correction method and circuit for checking error using error correction encoder
    US8739007B2|2014-05-27|Chien search using multiple basis representation
    JP5300170B2|2013-09-25|Reed-Solomon decoder circuit with forward Chien search method
    US4649541A|1987-03-10|Reed-Solomon decoder
    US8458574B2|2013-06-04|Compact chien-search based decoding apparatus and method
    US7313583B2|2007-12-25|Galois field arithmetic unit for use within a processor
    US4873688A|1989-10-10|High-speed real-time Reed-Solomon decoder
    US6539515B1|2003-03-25|Accelerated Reed-Solomon error correction
    US6640327B1|2003-10-28|Fast BCH error detection and correction using generator polynomial permutation
    US7249310B1|2007-07-24|Error evaluator for inversionless Berlekamp-Massey algorithm in Reed-Solomon decoders
    EP0365555B1|1993-03-17|Method and apparatus for error correction
    EP0567148B1|2002-07-03|Operating circuit for galois field
    US5517509A|1996-05-14|Decoder for decoding ECC using Euclid's algorithm
    AU603641B2|1990-11-22|Error correction method using reed-solomon code
    JP5043562B2|2012-10-10|Error correction circuit, method thereof, and semiconductor memory device including the circuit
    US5020060A|1991-05-28|Error code correction device having a galois arithmetic unit
    US20020056067A1|2002-05-09|Forward error corrector
    US6725416B2|2004-04-20|Forward error correction apparatus and methods
    同族专利:
    公开号 | 公开日
    KR100510503B1|2005-08-26|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2002-12-10|Application filed by 삼성전자주식회사
    2002-12-10|Priority to KR10-2002-0078389A
    2004-06-16|Publication of KR20040050536A
    2005-08-26|Application granted
    2005-08-26|Publication of KR100510503B1
    优先权:
    申请号 | 申请日 | 专利标题
    KR10-2002-0078389A|KR100510503B1|2002-12-10|2002-12-10|New pipline Reed Solomon decoding method for providing extreme hardware efficiency|
    [返回顶部]