← Back to Patent Explorer
US4852098A Expired / Lapsed US ⏱️ 0.0 years remaining

Polynomial operator in galois fields and a digital signal processor comprising an operator of this type

Assignee: Thales SA
•
Filing: 1987-10-22
•
Granted: 1989-07-25
•
Expires: 2007-10-22
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract The polynomial operator in the Galois field of the invention is organized at three levels: a multiplexer level to select and transmit the operands to be used for the successive stage of the calculation to a second level; a so-called pipeline level comprising 3 flip-flop registers to memorize the operands selected at the first level; a third level for calculation, comprising a multiplier-adder which has its inputs X, Y and Z connected to the outputs of the registers, and which gives the coefficients of the resultant polynomials in the Galois field while always performing the same calculation by repetition of the same control instruction. This operator can be applied to digital telecommunications for the encoding and decoding of BCH or RS (REED SOLOMON) error-correcting codes, and can be used to make an integrated processor capable of processing digital data in the form of octets.

Inventors

  • 👤 Dominique Brechard
  • 👤 Pierre-Andre Laurent

Bibliographic Details

Application Number —
Jurisdiction US
Data Source google_patents
Last Synchronized 2026-11-02 02:05
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/033; G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724

Claims Analysis

Total Claims: 7
Claim 1
Independent Claim 210 words
A polynomial operator in Galois fields organized at three successive levels: a first level for the selection of operands comprising a multiplexing circuit, with three Balois value outputs; a so-called "pipeline" level, comprising three memory registers having three multiple inputs connected to the outputs of the multiplexing circuit, to memorize three operands, along with three associated outputs; and a calculating level comprising a multiplier/adder circuit in said Galois fields, the said circuit comprising two multiplier inputs, connected to the outputs of two of the memory registers, one adder input, connected to the output of the third memory register, the multiplier/adder circuit always performing the calculation X+(Y×Z) where + and × represent addition and multiplication in said Galois fields, said multiplier/adder circuit outputting a result output; and wherein the inputs of the multiplexing circuit are inputs of operands to receive Galois values from outside the operator, with, in addition, at least one input connected to the output of one of the memory registers, and one input connected to the result output of the multiplier/adder, the selection of one of the three inputs of the multiplexing circuit being programmed so that the calculating instruction X+(Y×Z) is unchanged regardless of the type of polynomial operation to be performed in a particular Galois field.
Claim 2
Dependent Claim 210 words
A polynomial operator in Galois fields organized at three successive levels: a first level for the selection of operands comprising a multiplexing circuit, with three Balois value outputs; a so-called "pipeline" level, comprising three memory registers having three multiple inputs connected to the outputs of the multiplexing circuit, to memorize three operands, along with three associated outputs; and a calculating level comprising a multiplier/adder circuit in said Galois fields, the said circuit comprising two multiplier inputs, connected to the outputs of two of the memory registers, one adder input, connected to the output of the third memory register, the multiplier/adder circuit always performing the calculation X+(Y×Z) where + and × represent addition and multiplication in said Galois fields, said multiplier/adder circuit outputting a result output; and wherein the inputs of the multiplexing circuit are inputs of operands to receive Galois values from outside the operator, with, in addition, at least one input connected to the output of one of the memory registers, and one input connected to the result output of the multiplier/adder, the selection of one of the three inputs of the multiplexing circuit being programmed so that the calculating instruction X+(Y×Z) is unchanged regardless of the type of polynomial operation to be performed in a particular Galois field.
Claim 3
Dependent Claim 66 words
An operator according to claim 1, wherein: the multiplexing circuit has two inputs of operands, the first register being always fed by the same operand input, a second register being fed by either of the operand inputs or by the result output via a multiplexer, the third register being fed by an operand input through the result output or through the output of the second register.
Claim 4
Dependent Claim 79 words
An operator according to claim 1, wherein: since each operand Galois value at the input of the operator is allocated an additional validity bit, the operator further comprises a processing circuit for validity bits, having one-bit memories associated with each of the validity bits of the input operands, control inputs and an output giving the validity bit to be assigned to the result output of the multiplier-adder to form the result output available at the output of the operator.
Claim 5
Dependent Claim 80 words
An operator according to claim 1, wherein: in processing Galois values in one of the five Galois fields with 16, 32, 64, 128 or 256 elements, respectively comprising elements with 4, 5, 6, 7 or 8 significant bits, the multiplier-adder circuit has 5 circuits for the division of the result obtained from a maximum of 15 bits, respectively by the generator polynomials of these field to carry the results to the equivalent Galois values having a maximum of 8 bits.
Claim 6
Dependent Claim 22 words
An operator according to claim 1, wherein: a resultant integrated structure having at least 9 active layers as made by VLSI technology.
Claim 7
Dependent Claim 27 words
An operator according to claim 1 wherein: a digital signal processor capable of being parameterized encodes and/or decodes BCH and REED SOLOMON error correcting and detecting codes.

References Cited (Backward Citations)

US4099160A Cited
US4165444A Cited
US4162480A Cited
US4117458A Cited
US4498175A Cited
US4527269A Cited
EP0165147A1 Cited

USPTO Annuity & Maintenance Windows

Annuity Stage Window Opens Payment Deadline Surcharge Period Until Estimated Fee Status
3.5 Years (Year 4) 1992-07-24 1993-01-23 1993-07-25 $2000.00 Window Closed / Lapsed
7.5 Years (Year 8) 1996-07-24 1997-01-23 1997-07-25 $3760.00 Window Closed / Lapsed
11.5 Years (Year 12) 2000-07-24 2001-01-23 2001-07-25 $7700.00 Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag