Back to results
US 8,806,308 B2Granted
Bose-Chaudhuri-Hocquenghem (BCH) decoder
AssigneeFreescale Semiconductor, Inc.
InventorAnkush Srivastava
Life of this patent
Estimating the term…
Abstract
A decoder for decoding a set of bits encoded using a Bose-Chaudhuri-Hocquenghem (BCH) error-correcting code (ECC) includes a syndrome generator, a key equation solver, and an error bit locator. The syndrome generator receives the set of encoded bits and generates a set of syndromes. The key equation solver generates an error location polynomial based on the set of syndromes. The error bit locator generates an error match bit using the error location polynomial, and the error match bit is used to identify and correct errors in the set of encoded bits.
Claims20
A decoder, comprising:
- a syndrome generator for receiving a set of encoded bits and generating a corresponding set of syndromes based on a clock signal;
- a key equation solver, connected to the syndrome generator, for determining an error location polynomial using the set of syndromes, wherein the key equation solver determines first through fourth coefficients of the error location polynomial, and wherein each of the first through fourth coefficients include first through fifth bits, wherein the key equation solver comprises:
- a first polynomial basis multiplier circuit for determining a first product that is a product of first and second syndromes;
- a first finite field inversion circuit for determining a first inverse that is a multiplicative inverse of the first syndrome;
- a first finite field adder circuit, connected to the first polynomial basis multiplier circuit, for determining a first finite field sum that is a sum of the first product and a third syndrome;
- a second finite field inversion circuit connected to the first adder circuit, for determining a second inverse that is a multiplicative inverse of the first sum;
- a second polynomial basis multiplier circuit, connected to the first adder circuit and the first inversion circuit, for determining a second product that is a product of the first sum and the first inverse;
- a third polynomial basis multiplier circuit, connected to the second polynomial basis multiplier circuit, for determining a third product that is a product of the second product and the third syndrome;
- a fourth polynomial basis multiplier circuit for determining a fourth product that is a product of the first syndrome and a fourth syndrome;
- a second finite field adder circuit, connected to the fourth polynomial basis multiplier circuit, for determining a second finite field sum that is a sum of the fourth product and a fifth syndrome;
- a third finite field adder circuit, connected to the second finite field adder circuit and the third polynomial basis multiplier circuit, for determining a third finite field sum that is a sum of the third product and the second finite field sum;
- a fifth polynomial basis multiplier circuit, connected to the third finite field adder circuit and the second finite field inversion circuit, for determining a fifth product that is a product of the third finite field sum and the second finite field inverse;
- a fourth finite field adder circuit, connected to the second and fifth polynomial basis multiplier circuits, for determining a fourth finite field sum that is a sum of the second and fifth products;
- and
- a sixth polynomial basis multiplier circuit, connected to the fifth polynomial basis multiplier circuit, for determining a sixth product that is a product of the fifth product and the first syndrome,
- wherein the first coefficient is the first syndrome, the second coefficient is the fourth finite field sum, the third coefficient is the sixth product, and the fourth coefficient is binary one;
- a serial bit register for receiving the set of encoded bits and outputting an encoded bit at each active edge of the clock signal;
- an error bit locator, connected to the key equation solver, for identifying an erroneous encoded bit by generating an error match bit based on the first through fourth coefficients of the error location polynomial;
- and
- a first XOR gate, connected to the serial bit register and the error bit locator, for generating a decoded bit based on the encoded bit and the error match bit.
17 more elements
A memory device, comprising:
- a Bose-Chaudhuri-Hocquenghem (BCH) decoder for rectifying soft errors in the memory device, the BDH decoder comprising:
- a syndrome generator for receiving a set of encoded bits and generating a corresponding set of syndromes based on a clock signal;
- a key equation solver, connected to the syndrome generator, for determining an error location polynomial using the set of syndromes, wherein the key equation solver determines first through fourth coefficients of the error location polynomial, and wherein each of the first through fourth coefficients include first through fifth bits, wherein the key equation solver comprises:
- a first polynomial basis multiplier circuit for determining a first product that is a product of first and second syndromes;
- a first finite field inversion circuit for determining a first inverse that is a multiplicative inverse of the first syndrome;
- a first finite field adder circuit, connected to the first polynomial basis multiplier circuit, for determining a first finite field sum that is a sum of the first product and a third syndrome;
- a second finite field inversion circuit connected to the first adder circuit, for determining a second inverse that is a multiplicative inverse of the first sum;
- a second polynomial basis multiplier circuit, connected to the first adder circuit and the first inversion circuit, for determining a second product that is a product of the first sum and the first inverse;
- a third polynomial basis multiplier circuit, connected to the second polynomial basis multiplier circuit, for determining a third product that is a product of the second product and the third syndrome;
- a fourth polynomial basis multiplier circuit for determining a fourth product that is a product of the first syndrome and a fourth syndrome;
- a second finite field adder circuit, connected to the fourth polynomial basis multiplier circuit, for determining a second finite field sum that is a sum of the fourth product and a fifth syndrome;
- a third finite field adder circuit, connected to the second finite field adder circuit and the third polynomial basis multiplier circuit, for determining a third finite field sum that is a sum of the third product and the second finite field sum;
- a fifth polynomial basis multiplier circuit, connected to the third finite field adder circuit and the second finite field inversion circuit, for determining a fifth product that is a product of the third finite field sum and the second finite field inverse;
- a fourth finite field adder circuit, connected to the second and fifth polynomial basis multiplier circuits, for determining a fourth finite field sum that is a sum of the second and fifth products;
- and
- a sixth polynomial basis multiplier circuit, connected to the fifth polynomial basis multiplier circuit, for determining a sixth product that is a product of the fifth product and the first syndrome,
- wherein the first coefficient is the first syndrome, the second coefficient is the fourth finite field sum, the third coefficient is the sixth product, and the fourth coefficient is binary one;
- a serial bit register for receiving the set of encoded bits and outputting an encoded bit at each active edge of the clock signal;
- an error bit locator, connected to the key equation solver, for identifying an erroneous encoded bit by generating an error match bit based on the first through fourth coefficients of the error location polynomial;
- and
- a first XOR gate, connected to the serial bit register and the error bit locator, for generating a decoded bit based on the encoded bit and the error match bit.
18 more elements
Dependencies are inferred from the claim text.