FIFO based parity generator

A parity generator for generating a block of m parity bits from a series of K data blocks, each one of the K data blocks comprising a series of m bits, the m bits of each data block being arranged to form P words, each word having n bits, the parity generator including n circuits with each circuit comprising:

• an XOR logic device having first and second inputs and an output, the first input coupled to the P words of the K data blocks to receive one of the n bits;
• a parity bit storage device comprising a series of P one bit memory locations arranged as a FIFO data structure, the parity bit storage device having an output coupled to the second input of the XOR logic device and an input coupled to the output of the XOR logic device;
• a write/read address generator coupled to the storage device, the write/read address generator having a read control input and a write control input;
• the write control input adapted to receive a FIFO write signal that causes the write/read address generator to control the storage device to store a signal output by the XOR logic device, in the storage device in the FIFO manner, the signal comprising the logical result of XORing the first and second X0R inputs to provide a parity bit signal;
• the read control input adapted to receive a FIFO read signal that causes the write/read address generator to control the storage device to output the parity bit signal stored in the storage device, in the FIFO manner.

A parity generator for generating a block of m parity bits from a series of K data blocks, each one of the K data blocks comprising a series of m bits, the parity generator comprising:

• an XOR logic device including,
• a) a first input to receive a series of one bit parity.sub.-- block signals,
• b) a second input coupled to the K data blocks to receive a series of input signals each input signal comprising one of the series of m bits of data comprising one of the K data blocks, and
• c) a parity bit output for outputting a series of one bit parity signals generated by the XOR logic device by performing a logical XOR operation on each one of the parity.sub.-- block signals in the series of signals received by the first signal input, and each corresponding input signal in the series of input signals supplied to the second signal input of the XOR logic device;
• and
• a logic block comprising m one bit storage locations arranged in a FIFO data structure for storing the one bit parity signals output by the XOR logic device, the logic block includes
• a) a first input to receive a FIFO read enable signal, to enable the logic block to output one of m values stored in the logic block's m one bit storage locations as a function of the FIFO read enable signal and the FIFO data structure,
• b) a second input to receive a FIFO write enable signal, to enable the logic block to store the series of one bit parity signals output by the XOR logic device in one of the logic block's m one bit storage locations as a function of the FIFO write enable signal and the FIFO data structure,
• c) a parity bit input coupled to the parity bit output of the XOR logic device, and
• d) a parity.sub.-- block signal output coupled to the first input of the XOR logic device and for outputting the series of m one bit parity signals stored in the logic block's m one bit storage locations.

A parity generator for generating a block of parity bits from a series of K data blocks, each one of the K data blocks comprising a series of m bits, the parity generator comprising:

• i) a buffer including,
• a parity.sub.-- block signal input for receiving a series of parity.sub.-- block signals,
• b) a parity generator parity signal output for outputting a series of one bit parity signals, and
• c) an enable input to receive an output enable signal, to enable the parity generator parity signal output as a function of the output enable signal;
• ii) an XOR logic device including,
• a) a first input to receive a series of one bit parity.sub.-- block signals,
• b) a second input coupled to the K data blocks to receive a series of input signals, each one of the series of input signals comprising one of the series of m bits of data comprising one of the K data blocks, and
• c) a parity bit output for outputting a series of one bit parity signals generated by the XOR logic device by performing a logical XOR operation on each one of the parity.sub.-- block signals in the series of parity.sub.-- block signals received by the first signal input, and each corresponding input signal in the series of input signals supplied to the second signal input of the XOR logic device;
• and
• iii) a logic block comprising m one bit storage locations arranged in a FIFO data structure for storing the one bit parity signals output by the XOR logic device, the logic block includes
• a) a first input to receive a FIFO read enable signal, to enable the logic block to output one of m values stored in the logic block's m one bit storage locations as a function of the FIFO read enable signal and the FIFO data structure,
• b) a second input to receive a FIFO write enable signal, to enable the logic block to store the series of one bit parity signals output by the XOR logic device in one of the logic block's m one bit storage locations as a function of the FIFO write enable signal and the FIFO data structure,
• c) a parity bit input coupled to the parity bit output of the XOR logic device, and
• d) a parity.sub.-- block signal output coupled to the first input of the XOR logic device and to the parity.sub.-- block signal input of the buffer.

A parity generator for generating a block of m parity bits from a series of K data blocks, each one of the K data blocks comprising m bits arranged to form P words, each word having n bits the parity generator comprising:

• a bus comprising n lines coupled to the K data blocks;
• a plurality of n one bit parity generator circuits, each one of the n one bit parity generator circuits having an input and an output coupled to a respective one of the n lines of the bus, each one of the one bit parity generator circuits comprising,
• i) an XOR logic device including,
• a) a first input to receive a series of one bit parity.sub.-- block signals,
• b) a second input coupled to the input of the one bit parity generator circuit to receive a series of input signals from the respective line of the bus, each input signal comprising one of the series of n bits comprising one of the P words of data comprising one of the K data blocks, and
• c) a parity bit output for outputting the series of one bit parity signals generated by the XOR logic device by performing a logical XOR operation on each one of the parity.sub.-- block signals in the series of parity.sub.-- block signals received by the first signal input, and each corresponding input signal in the series of input signals supplied by the line of the bus to the second signal input of the XOR logic device;
• and
• ii) a logic block comprising P one bit storage locations arranged in a FIFO data structure for storing the one bit parity signals output by the XOR logic device, the logic block includes,
• a) a first input to receive a FIFO read enable signal, to enable the logic block to output one of P values stored in the logic block's P one bit storage locations as a function of the FIFO read enable signal and the FIFO data structure,
• b) a second input to receive a FIFO write enable signal, to enable the logic block to store the series of one bit parity signals output by the XOR logic device in one of the logic block's P one bit storage locations as a function of the FIFO write enable signal and the FIFO data structure,
• c) a parity bit input coupled to the parity bit output of the XOR logic device, and
• d) a parity.sub.-- block signal output coupled to the first input of the XOR logic device and coupled to the output of the one bit parity generator circuit.

A computer system, comprising:

• a bus comprising n data lines and a series of control lines;
• a data storage device coupled to the bus for storing a series of K data blocks, each data block comprising m bits arranged to form P words, each one of the P words comprising a series of n bits;
• a parity generator coupled to the bus for generating a block of m parity bits from the series of K data blocks, the parity generator comprising
• a plurality of n one bit parity generator circuits, each parity generator circuit comprising,
• i) an input and an output being coupled to a respective one of the n data lines of the bus,
• ii) an XOR logic device including,
• a) a first input to receive a series of one bit parity.sub.-- block signals,
• b) a second input coupled to the input of the one bit parity generator circuit to receive a series of input signals from the respective data line of the bus each input signal comprising a respective one of the series of n bits comprising one of the P words of data comprising one of the K data blocks, and
• c) a parity bit output for outputting the series of one bit parity signals generated by the XOR logic device by performing a logical XOR operation on each one of the parity.sub.-- block signals in the series of parity.sub.-- block signals received by the first signal input, and each corresponding input signal in the series of input signals supplied by the respective line of the bus to the second signal input of the XOR logic device;
• and
• iii) a logic block comprising P one bit storage locations arranged in a FIFO data structure for storing the one bit parity signals output by the XOR logic device, the logic block includes
• a) a first input to receive a FIFO read enable signal, to enable the logic block to output one of P values stored in the logic block's P one bit storage locations as a function of the FIFO read enable signal and the FIFO data structure,
• b) a second input to receive a FIFO write enable signal, to enable the logic block to store the series of one bit parity signals output by the XOR logic device in one of the logic block's P one bit storage locations as a function of the FIFO write enable signal and the FIFO data structure,
• c) a parity bit input coupled to the parity bit output of the XOR logic device, and
• d) a parity.sub.-- block signal output coupled to the first input of the XOR logic device and coupled to the one bit parity generator output for outputting the series of one bit parity signals stored in the logic block's P one bit storage locations;
• and
• a control logic block for controlling the operation of the parity generator, the control logic block comprising,
• a) an input coupled to the bus's control and data lines for receiving control and data signals from the bus,
• b) a FIFO read enable signal output coupled to the first input of each one of the n one bit parity generator circuits'logic blocks, and
• c) a FIFO write enable signal output coupled to the second input of each one of the n one bit parity generator circuits'logic blocks.

A method for generating a block of m parity bits from a series of K data blocks, each one of the K data blocks comprising m bits, the method for generating the parity block comprising the steps of:

• a) XORing every bit in the first of the series of K data blocks with logical "0" to create a current parity block;
• b) storing the resulting current parity block in a FIFO data structure contained in a logic block comprising m one bit memory locations;
• c) sequentially XORing the first through m.sup.th bits of the stored parity block with the first through m.sup.th bits of the next data block in the series of K data blocks not previously used in the XOR operation to form a new current parity block;
• d) storing the new current parity block in the FIFO data structure;
• e) repeating steps (c) and (d) until there are no remaining data blocks in the series of K data blocks upon which to perform the logical XOR operation, the stored parity block in the FIFO data structure comprising the parity block generated from the series of K data blocks.

A method for generating a block of m parity bits from a series of K data blocks, each one of the K data blocks comprising a series of n bits, the method comprising the steps of:

• storing the n bits of a first one of the K data blocks in a FIFO manner;
• sequentially reading each one of the stored n bits of the first one of the K data blocks in a FIFO manner;
• for each read bit, XORing the read bit with a corresponding one of the n bits of a second one of the K data blocks, to provide a corresponding one of the n parity bits;
• and
• sequentially storing each one of the n parity bits in a FIFO manner.