Parallel cyclic redundancy checking circuit

Abstract

A parallel cyclic redundancy checking circuit which determines the validity of digital, binary, cyclical data. The parallel structure of this circuit enables it to check high frequency data. Shift registers store sequentially occurring parallel groups of data and a feedback network comprising exclusive-or gates provides a coding arrangement which produces a resultant data pattern to indicate the validity of the cyclical parallel input data. Resultant data patterns are periodically stored in a random-access-memory which initializes the shift registers to provide a time sharing operation. A comparator detects invalid data by comparing the resultant patterns with expected values.

What is claimed is: 
     
       1. A cyclic redundancy checking circuit for use in a data verification system including a data generator operated to provide a plurality of repetitive series of groups of parallel data bits, normally having predetermined values, and a signal generator operated to periodically provide load and write signals both associated with each group of parallel data bits and further operates to periodically provide comparator enable and read signals, both associated with each series of groups of parallel data bits, said cyclic redundancy checking circuit comprising: first coding means connected to said data generator, operable to provide a first coded signal associated with each group of parallel data bits;   first-in-first-out storage means of predetermined capacity connected to said signal generator and said first coding means, said storage means capable of being initialized in response to said load signal, and operative to store a predetermined number of said first coded signals and further operative to provide a storage signal associated with each stored first coded signal;   second coding means connected to said storage means, operative in response to said storage signal to provide a second coded signal;   said first coding means further connected to said second coding means, operative in response to each group of parallel data bits and said second coded signal to provide said first coded signal;   first memory means, connected to said storage means and said signal generator, operative in response to said write signal to store said storage signal, further operative in response to said load signal to read out said storage signal;   said storage means operative in response to said load signal to store said displayed storage signal, whereby said storage means is initialized;   second memory means connected to said signal generator, storing a plurality of predetermined memory signals, operative in response to each read signal to readout a predetermined memory signal; and   comparison means connected to said storage means, said signal generator and said second memory means, operative in response to said comparator enable signal to compare said memory signal to said storage signal, whereby a failure in said repetitive series of groups of parallel data bits is detected.   
     
     
       2. A cyclic redundancy checking circuit as claimed in claim 1, wherein said signal generator periodically operates to provide a select signal associated with each group of parallel data bits, said cyclic redundancy checking circuit further comprising: a plurality of data selectors each connected to said signal generator and further connected between said data generator and said first coding means, each operative in response to said select signal to gate a first selected data bit of each group of parallel data bits to said first coding means, and further operative in response to an absence of said select signal to gate a second selected data bit of each group of parallel data bits to said first coding means. 
     
     
       3. A cyclic redundancy checking circuit as claimed in claim 2, wherein said first coding means comprises: a first plurality of exclusive-or gates, each connected to an associated one of said data selectors, each operative to provide first or second coded data bits associated with said first or second selected data bits, respectively. 
     
     
       4. A cyclic redundancy checking circuit as claimed in claim 3, wherein said signal generator further operates to provide a clock signal associated with each group of parallel data bits, said storage means comprising: a plurality of shift registers each having a clock input, and a clear input, both connected to said signal generator, each shift register further having a serial input connected to an associated one of said plurality of exclusive-or gates, and each shift register further having a plurality of parallel inputs connected to said first memory means and a plurality of associated bit positions and outputs; each shift register operative in response to said comparator enable signal to provide a logic level 0 signal on each output; each shift register further operative to sequentially store each first and second coded data bit, on an alternating basis, in response to each alternate clock pulse; each shift register further operative to shift all stored data bits by one bit position, in response to each clock pulse; each shift register further operative in response to said load signal to store said displayed storage signal, whereby said storage means is initialized via said parallel inputs; and each shift register further operative to provide a plurality of stored data bit signals on said plurality of outputs.   
     
     
       5. A cyclic redundancy checking circuit as claimed in claim 4, wherein each shift register has at least three outputs, said second coding means comprising: a second plurality of exclusive-or gates each having first and second inputs, each of said second plurality having its first input connected to a first output of a first associated shift register, each of said second plurality having its second input connected to a second output of a second associated shift register; and   a third plurality of exclusive-or gates, each having first and second inputs, each of said third plurality having its first input connected to an associated one of said second plurality of exclusive-or gates, and each of said third plurality having its second input connected to a third output of a third associated shift register, each of said second and third pluralities of said exclusive-or gates operative in combination, in response to said stored data bit signals appearing at said first, second and third outputs to provide a third coded data bit.   
     
     
       6. A cyclic redundancy checking circuit as claimed in claim 5, wherein: said first plurality of exclusive-or gates is further connected to an associated one of said third plurality of exclusive-or gates, each of said first plurality of exclusive-or gates operated in response to said third coded data bit and said first or second selected data bits, to provide said first or second coded data bit, respectively. 
     
     
       7. A cyclic redundancy checking circuit as claimed in claim 2, wherein each group of parallel data bits includes eight bits, said plurality of data selectors includes four data selectors each associated with two of said parallel data bits. 
     
     
       8. A cyclic redundancy checking circuit as claimed in claim 3, wherein said first plurality of exclusive-or gates includes four such gates. 
     
     
       9. A cyclic redundancy checking circuit as claimed in claim 4, wherein said storage means comprises: four 4-bit shift registers each having four outputs.   
     
     
       10. A cyclic redundancy checking circuit, as claimed in claim 1, wherein said first memory means comprises: a random-access memory connected to an address counter.   
     
     
       11. A cyclic redundancy checking circuit as claimed in claim 1, wherein said second memory means comprises: a read-only memory connected to an address counter.   
     
     
       12. A cyclic redundancy checking circuit as claimed in claim 1, wherein said comparison means comprises a digital comparator.