Fast diagonal interleaved parity (DIP) calculator

• US 7,191,388 B1
• Filed: 03/01/2004
• Issued: 03/13/2007
• Est. Priority Date: 03/01/2004
• Status: Active Grant

• 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:
  US10/791,073
• Time in Patent Office: 1,107 Days
• Field of Search: 714/801
• US Class Current: 714/801
• 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 the 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, wherein the programmable device is configured to sequentially process the packet a predetermined number of words at a time, the programmable device comprising:

a plurality of programmable blocks, one or more of the programmable blocks being configured to implement a set of XOR calculation chains, the one or more programmable blocks being configured such that the 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 1, wherein each data word and the control word of the external bus is sixteen-bits wide.

7. 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 ordered 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 an intermediate DIP parity word.

8. The method of claim 7, further comprising adjusting the intermediate DIP parity word according to the number of words that were assigned values of logical zeroes to provide the DIP word.

9. The method of claim 8, wherein the bus is a SPI4-2 bus, each word is sixteen bits wide, and the set of diagonal XOR calculation chain comprises sixteen XOR calculation chains.

10. The method of claim 9, wherein the adjustment of the intermediate 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. The method of claim 9, wherein the DIP parity word is a sixteen-bit parity word, the method further comprising collapsing the sixteen-bit parity word into a 4-bit DIP4 parity word.

12. The method of claim 11, wherein the adjustment of the intermediate DIP parity word comprises shifting the bits of the 4-bit DIP4 parity word to the left one bit for each word that was assigned values of logical zeroes.

13. The method of claim 11, wherein the packet is a SPI4-2 received packet, the method further comprising:

before propagating the diagonal XOR calculation chains through the sample of words containing the control word;

storing the least four significant bits of the control word; and

assigning the least four significant bits of the control word to logical ones.

14. The method of claim 13, further comprising:

comparing the stored four bits of the control word to the DIP4 parity word to determine whether the packet was received correctly.

15. The method of claim 11, wherein the packet is a SPI4-2 received packet, the method further comprising:

forming the logical AND product of the bits in the DIP4 parity word to determine whether the packet was received correctly.

16. The method of claim 11, wherein the packet is to be a SPI4-2 transmitted packet, the method further comprising:

replacing the least four significant bits of the control word with the DIP4 parity word; and

transmitting the data words and the control word in the packet.