Variable T BCH encoding

• US 10,236,915 B2
• Filed: 07/21/2017
• Issued: 03/19/2019
• Est. Priority Date: 07/29/2016
• Status: Active Grant

• Current Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Original Assignee: Microsemi Solutions (U.S.), Inc. (Microchip Technology Incorporated)
• Inventors: Graumann, Peter John Waldemar, Fard, Saeed Fouladi
• Primary Examiner(s): Abraham, Esaw T
• Application Number:
  US15/657,020
• Publication Number:
  US 20180034483A1
• Time in Patent Office: 606 Days
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H03M 13/6356 by repetition or insertion of dummy data, i.e. rate reduction
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Abstract

A system for implementing variable T BCH encoders includes: a polynomial multiplier for multiplying a message polynomial by a difference polynomial to achieve a first value, wherein the message polynomial comprises data bits as coefficients and the difference polynomial comprises minimal polynomials that are present in a T error correcting code and are absent from a T−ΔT error correcting BCH code; a shifter/zero-padder coupled with the BCH encoder, the shifter/zero-padder for multiplying the first value by x^{N-{tilde over (K)}} to achieve a second value; a BCH encoder coupled with the polynomial multiplier, the BCH encoder for dividing the second value by a generator polynomial of the T error correcting BCH code and calculating a remainder based on the dividing to achieve a third value; and a polynomial divider for dividing the third value by the difference polynomial to achieve a fourth value comprising parity of the T−ΔT error correcting BCH code.

Claims

1. A method comprising:

receiving a message polynomial comprising data bits as coefficients;

multiplying, using a polynomial multiplier/divider module, said message polynomial by a difference polynomial to achieve a first value, wherein said difference polynomial comprises minimal polynomials that are present in a T error correcting BCH code and are absent from a T−

Δ

T error correcting BCH code;

multiplying, using a shifter/zero-padder, said first value by x^{N-{tilde over (K)}} to achieve a second value;

dividing said second value by a generator polynomial of said T error correcting BCH code and calculating a remainder based on said dividing to achieve a third value, said dividing and calculating performed by a BCH encoder circuit;

dividing, using said polynomial multiplier/divider module, said third value by said difference polynomial to achieve a fourth value comprising parity of said T−

Δ

T error correcting BCH code, the dividing of said third by value by said difference polynomial performed after said multiplying by said multiplier/divider module is complete; and

outputting from said memory controller said fourth value.

2. The method of claim 1, wherein said outputting said fourth value further comprises sending said fourth value to a memory storage area.

3. The method of claim 1, wherein said outputting said fourth value further comprises sending said fourth value to a memory chip that is coupled to said memory controller, the method further comprising storing said fourth value in memory cells of said memory chip.

4. The method of claim 1 wherein the polynomial multiplier/divider module further comprises a circuit for operation as a linear feed forward shift register and for operation as a linear feedback shift register.

5. The method of claim 1, wherein Δ

T is one.

6. The method of claim 1, wherein Δ

T is more than one.

7. A system comprising:

a polynomial multiplier/divider module for multiplying a message polynomial by a difference polynomial to achieve a first value, wherein said message polynomial comprises user data bits as coefficients and said difference polynomial comprises minimal polynomials that are present in a T error correcting code and are absent from a T−

Δ

T error correcting BCH code;

a shifter/zero-padder coupled with said polynomial multiplier/divider module, said shifter/zero-padder for multiplying said first value by x^{N-{tilde over (K)}} to achieve a second value;

a BCH encoder circuit coupled with said shifter/zero-padder, said BCH encoder circuit for dividing said second value by a generator polynomial of said T error correcting BCH code and calculating a remainder based on said dividing to achieve a third value;

said polynomial multiplier/divider module further for dividing said third value by said difference polynomial to achieve a fourth value comprising parity of said T−

Δ

T error correcting BCH code after said multiplying said message polynomial by said difference polynomial; and

a parity output module for outputting said fourth value.

8. The system of claim 7, further comprising:

a receiver for receiving said message polynomial, said receiver coupled to said polynomial multiplier/divider module.

9. The system of claim 7, further comprising:

a parity output module coupled to said polynomial multiplier/divider module, said parity output module for outputting said fourth value.

10. The system of claim 7, further comprising:

a memory controller, said memory controller comprising said polynomial multiplier/divider, said shifter/zero-padder, and said BCH encoder.

11. The system of claim 10, wherein said system further comprises memory cells coupled to said memory controller, said memory cells configured to store said fourth value.

12. The system of claim 7, wherein Δ

T is more than one.

13. The system of claim 7, wherein Δ

T is one.

14. The system of claim 7, wherein said polynomial multiplier/divider module further comprises:

a first data block including a first polynomial multiplier/divider circuit;

a first multiplexer coupled to the output of said first polynomial multiplier/divider circuit;

a second data block coupled to the output of said first multiplexer, the second data block including a second polynomial multiplier/divider circuit; and

a second multiplexer coupled to the output of said second polynomial multiplier/divider circuit, the output of the second multiplexer coupled to said shifter/zero-padder.

15. A method comprising:

receiving a message polynomial comprising data bits as coefficients;

multiplying, using a polynomial multiplier circuit, said message polynomial by a difference polynomial to achieve a first value, wherein said difference polynomial comprises minimal polynomials that are present in a T error correcting BCH code and are absent from a T−

Δ

T error correcting BCH code;

multiplying, using a shifter/zero-padder, said first value by x^{N-{tilde over (K)}} to achieve a second value;

dividing said second value by a generator polynomial of said T error correcting BCH code and calculating a remainder based on said dividing to achieve a third value, said dividing said second value and said calculating performed by a BCH encoder circuit;

dividing, using a polynomial divider circuit, said third value by said difference polynomial to achieve a fourth value comprising parity of said T−

Δ

T error correcting BCH code, the dividing said third value performed after said multiplying by said polynomial multiplier circuit is complete; and

outputting from said memory controller said fourth value.

16. The method of claim 15, wherein said outputting said fourth value further comprises sending said fourth value to a memory storage area.

17. The method of claim 15, wherein said outputting said fourth value further comprises sending said fourth value to a memory chip that is coupled to the memory controller, the method further comprising storing the fourth value in memory cells of the memory chip.

18. A memory controller comprising:

a polynomial multiplier circuit for multiplying a message polynomial by a difference polynomial to achieve a first value, wherein said message polynomial comprises user data bits as coefficients and said difference polynomial comprises minimal polynomials that are present in a T error correcting code and are absent from a T−

Δ

T error correcting BCH code;

a shifter/zero-padder circuit coupled to said polynomial multiplier circuit, said shifter/zero-padder circuit for multiplying said first value by x^{N-{tilde over (K)}} to achieve a second value;

a BCH encoder circuit coupled with said shifter/zero-padder circuit, said BCH encoder circuit for dividing said second value by a generator polynomial of said T error correcting BCH code and calculating a remainder based on said dividing to achieve a third value;

a polynomial divider circuit coupled to said BCH encoder circuit for dividing said third value by said difference polynomial, after said multiplying said message polynomial by said difference polynomial, to achieve a fourth value comprising parity of said T−

Δ

T error correcting BCH code; and

a parity output module coupled to said polynomial output circuit, said parity output module for outputting said fourth value.

19. The memory controller of claim 18, wherein Δ

T is one.

20. The memory controller of claim 18, wherein Δ

T is more than one.

21. The memory controller of claim 18, wherein the polynomial multiplier comprises a linear feed forward shift register.

22. The memory controller of claim 18, wherein the polynomial divider comprises a linear feedback shift register.

23. The memory controller of claim 18, further comprising a receiver for receiving said message polynomial, said receiver coupled to said polynomial multiplier circuit.

24. The memory controller of claim 18,

wherein said polynomial multiplier circuit comprises:

a first polynomial multiplier;

a first multiplexer coupled to the output of said first polynomial multiplier;

a second polynomial multiplier coupled to the output of said first multiplexer; and

a second multiplexer coupled to the output of said second polynomial multiplier, the output of said second multiplexer coupled to said shifter/zero-padder; and

wherein said polynomial divider circuit comprises;

a first polynomial divider;

a third multiplexer coupled to the output of said first polynomial divider;

a second polynomial divider coupled to the output of said third multiplexer; and

a fourth multiplexer coupled to the output of said second polynomial divider, the output of the fourth multiplexer coupled to said parity output module.

25. The memory controller of claim 24, wherein said BCH encoder circuit comprises a first BCH encoder and a second BCH encoder and wherein said shifter/zero-padder circuit comprises a first a shifter/zero-padder and a second shifter/zero-padder, the output of said first shifter/zero-padder coupled to said first BCH encoder, and the output of said second shifter/zero-padder coupled to said second BCH encoder.