Diagonal interleaved parity calculator

• US 7,430,706 B1
• Filed: 02/16/2007
• Issued: 09/30/2008
• Est. Priority Date: 03/01/2004
• Status: Expired due to Fees

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Yuan, Shu, Peterson, Thomas A., Sallese, Kevin E.
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/676,071
• Time in Patent Office: 592 Days
• Field of Search: 714/758, 714/775, 714/781, 714/798, 714/807
• US Class Current: 714/807
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H03M 13/2721 the interleaver involves a diagonal direction, e.g. by using an interleaving matrix with read-out in a diagonal direction

Abstract

A method of calculating a diagonal interleaved parity word for groups of words sampled from a bus is provided, wherein a predetermined number of words are included in each sampling cycle. The bus carries successive data words that are followed by a control word. At each sampling cycle, diagonal XOR calculations chains are propagated through the words that were sampled. However, if a sampling cycle includes the control word, the words following the control word are assigned to logical zero values. The diagonal XOR calculation chains may then be terminated after processing the words in this sampling cycle to derive an intermediate diagonal parity word. The intermediate diagonal parity word may then be adjusted according to the number of words that were assigned logical zero values to calculate a second diagonal interleaved parity word.

Claims

1. A programmable device configured to calculate a diagonal interleaved parity word for a packet formed from a sequence of data words and ending in a control word, the programmable device comprising:

a plurality of programmable blocks, one or more of the programmable blocks being configured to propagate a set of diagonal XOR calculation chains through the packet to provide the diagonal interleaved parity word, the one or more programmable blocks being configured such that the diagonal XOR calculation chains have the same length regardless of the number of data words in the packet.

2. The programmable device of claim 1, wherein each programmable block is a look-up-table-based programmable block.

3. The programmable device of claim 1, wherein each programmable block is an AND-array-based programmable block.

4. The programmable device of claim 1, wherein the data words and the control words correspond to sequential samples of an external bus supporting a wire-line-level protocol.

5. The programmable device of claim 4, wherein the wire-line-level protocol is SPI4-2.

6. The programmable device of claim 4, wherein each data word and the control word of the external bus is sixteen-bits wide.

7. The programmable device of claim 4, wherein each sequential sample provides four words from a set consisting of the data words and the control word.

8. A method of calculating a diagonal interleaved parity (DIP) word from a packet formed from a succession of data words ordered from a first data word to a last data word, the packet ending in a control word, the method comprising:

successively sampling a predetermined number of words from the packet, wherein the first sample starts at the first data word;

for each successive sample of words, determining whether the control word is included in the sample;

if the control word is not included in the sample of words, propagating a set of diagonal XOR calculation chains through the sample; and

if the control word is included in the sample of words, assigning the words following the control word in the sample to logical zeroes and then propagating the set of diagonal XOR calculation chains through the sample of words to provide a DIP parity word.

9. The method of claim 8, wherein the provided DIP parity word is an intermediate DIP parity word, the method further comprising adjusting the intermediate DIP parity word to provide a second DIP parity word.

10. The method of claim 9, wherein the adjustment of the intermediate DIP parity word to provide the second DIP parity word comprises shifting the bits of the intermediate DIP parity word to the left one bit for each word that was assigned values of logical zeroes.

11. A programmable device configured to calculate a diagonal interleaved parity (DIP) word from a packet formed from a sequence of data words arranged from a first data word through a last data word, the packet ending in a control word, the programmable device comprising:

a plurality of programmable blocks, one or more of the programmable blocks being configured to sequentially process the packet by sampling an external bus an ordered sample of words at a time to form a first ordered sample through a last ordered sample, the first ordered sample beginning with the first data word, the last ordered sample containing the control word, wherein any words following the control word in the last ordered sample are assigned to logical zeroes, the one or more programmable blocks being configured to sequentially process the ordered samples by propagating a set of diagonal XOR calculation chains through each ordered sample to produce an intermediate DIP word and then adjusting the intermediate DIP word to produce a second DIP parity word.

12. The programmable device of claim 11, wherein each ordered sample of words comprises four ordered words.

13. The programmable device of claim 11, wherein the external bus is a SPI4-2 bus.

14. The programmable device of claim 13, wherein each data word and the control word of the SPI4-2 bus is sixteen-bits wide.