System and method for encoding using multiple linear feedback shift registers

• US 10,305,515 B1
• Filed: 02/02/2015
• Issued: 05/28/2019
• Est. Priority Date: 02/02/2015
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Weingarten, Hanan, Sabbag, Erez, Nassie, Amir
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US14/612,152
• Time in Patent Office: 1,576 Days
• CPC Class Codes: H03M 13/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/17 takes precedence
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

An encoder and a method for encoding a first stream of bits, the method may include splitting the first stream of bits to multiple second streams; encoding, in parallel and by using multiple linear feedback shift registers (LFSRs), the multiple second streams to provide third streams, wherein each second stream of the multiple second streams is encoded using an LFSR of the multiple LFSRs; wherein the encoding comprises feeding the multiple second streams to the multiple LFSRs; merging the third streams to provide a fourth stream; wherein the fourth stream is stored in the multiple LFSRs; and encoding the fourth stream to provide a fifth stream; wherein the encoding of the fourth stream comprises concatenating the multiple LFSRs while bypassing feedback circuits of some of the multiple LFSRs; and shifting the fourth stream through the multiple LFSRs.

Claims

1. A method for encoding a first stream of bits, comprising:

splitting with one or more switches, a first input stream of bits to multiple second streams;

encoding, in parallel and by using multiple linear feedback shift register (LSFR) circuits, the multiple second streams to provide third streams, wherein each second stream of the multiple second streams is encoded using an LFSR circuit of the multiple LFSR circuits;

wherein the encoding comprises feeding the multiple second streams to the multiple LFSR circuits;

merging, with memory cells, the third streams to provide a fourth stream;

wherein the fourth stream is stored in the multiple LFSR circuits; and

encoding the fourth stream to provide a fifth stream;

wherein the encoding of the fourth stream comprises concatenating the multiple LFSR circuits while bypassing feedback circuits of some of the multiple LFSR circuits; and

shifting the fourth stream through the multiple LFSR circuits.

2. The method according to claim 1, wherein the shifting of the fourth stream comprises performing multiple (M) shift operations, wherein M is a positive integer and equals an aggregate length of the multiple LFSR circuits.

3. The method according to claim 1, wherein the encoding of the multiple second streams comprises performing M/K shift operations, wherein K is a number of the multiple LFSR circuits.

4. The method according to claim 1, wherein the encoding of the multiple second streams comprises performing multiple (Q) zero shifting operation after feeding the multiple second streams to the multiple LFSR circuits;

wherein Q is a positive integer, and wherein the shifting of the fourth stream comprises performing (M−

J) shifting operations, wherein J is a positive integer and is responsive to Q, and wherein M equals an aggregate length of the LFSR circuits.

5. The method according to claim 4, wherein J equals Q*2.

6. The method according to claim 4, wherein Q is selected in response to a relationship between a length of each LFSR circuit and a length of each second stream.

7. The method according to claim 1, comprising determining whether to bypass at least one stage of each LFSR in response to a relationship between a length of each LFSR circuit and a length of each second stream.

8. The method according to claim 1, wherein the merging of the third streams comprises concatenating sets of bits, wherein each set of bits comprises bits that are located at a same respective location in each one of the different third streams, wherein an order of the sets of bits corresponds to respective locations of bits of the sets of bits.

9. The method according to claim 1, wherein the merging of the third streams is executed during a single clock cycle.

10. The method according to claim 1, wherein a number of the multiple second streams is a power of two.

11. An encoder implemented on one or more integrated circuit devices for encoding a first stream of bits, comprising:

multiple linear feedback shift register (LSFR) circuits;

logic, coupled to the multiple LFSR circuits, wherein the logic is configured to;

split, with one or more switches, the first stream of bits to multiple second streams; and

feed the multiple second streams to the multiple LFSR circuits in parallel;

wherein the multiple LFSR circuits are configured to encode, in parallel, the multiple second streams to provide third streams, wherein each second stream of the multiple second streams is encoded using an LFSR circuit of the multiple LFSR circuits;

wherein the logic is configured to;

merge the third streams to provide a fourth stream;

wherein the fourth stream is stored in memory cells of the multiple LFSR circuits; and

concatenate the multiple LFSR circuits while bypassing feedback circuits of some of the multiple LFSR circuits;

wherein at least one of the multiple LFSR circuits is configured to encode the fourth stream to provide a fifth stream;

wherein the logic is configured to shift the fourth stream through memory cells of the multiple LFSR circuits during the encoding of the fourth stream.

12. The encoder according to claim 11, wherein the encoder is configured to perform, during the encoding of the fourth stream, multiple (M) shift operations of the fourth stream, wherein M is a positive integer and equals an aggregate length of the multiple LFSR circuits.

13. The encoder according to claim 11, wherein the encoding of the multiple second streams comprises performing M/K shift operations, wherein K is a number of the multiple LFSR circuits.

14. The encoder according to claim 11 wherein the encoder is configured to perform multiple (Q) zero shifting operation after feeding the multiple second streams to the multiple LFSR circuits;

wherein Q is a positive integer, and wherein a shifting of the fourth stream comprises performing (M−

J) shifting operations, wherein J is a positive integer and is responsive to Q and wherein M equals an aggregate length of the multiple LFSR circuits.

15. The encoder according to claim 14, wherein J equals Q*2.

16. The encoder according to claim 14, wherein Q is selected in response to a relationship between a length of each LFSR circuit and a length of each second stream.

17. The encoder according to claim 11, wherein the encoder is configured to determine whether to bypass at least one stage of LFSR circuit in response to a relationship between a length of each LFSR circuit and a length of each second stream.

18. The encoder according to claim 11, wherein the encoder is configured to merge the third streams by concatenating sets of bits, wherein each set of bits comprises bits that are located at a same respective location in each one of the different third streams, wherein an order of the sets of bits corresponds to respective locations of bits of the sets of bits.

19. The encoder according to claim 11, wherein the merging of the third streams is executed during a single clock cycle.

20. The encoder according to claim 11, wherein a number of the multiple second streams is a power of two.