High speed Hamming code circuit and method for the correction of error bursts

• US 4,276,647 A
• Filed: 08/02/1979
• Issued: 06/30/1981
• Est. Priority Date: 08/02/1979
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Thacker, Charles P., Rider, Ronald E., Norman, Fielding M.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US06/063,022
• Time in Patent Office: 698 Days
• Field of Search: 371/38, 371/40, 371/37
• US Class Current: 714/762
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes

Abstract

A circuit and method for the high speed generation and comparison of Hamming codes to enable the correction of an error burst is described. The circuit generates or compares n Hamming codes simultaneously with the data field transmission. Each code word is associated with a data field word comprising every n^th bit. The resultant system corrects error bursts of up to n bits.

Additional circuitry is included to enable the correction of error bits in parallel, increasing the system bandwidth.

Claims

1. A circuit, comprising an input and an output, for transmitting a data field comprising a serial bit stream and for simultaneously generating Hamming codes to be used for correcting an n bit error burst in said data field comprising:

m storage means, each for serially storing n bits of binary data,

an exclusive OR gate for each storage means, the output of each exclusive OR gate coupled to the storage means input, the output of each storage means coupled to one input of its associated exclusive OR gate, and the other input of said exclusive OR gate coupled to said circuit input,

an m bit counter for enabling said exclusive OR gates in binary count order, said counter incrementing every n^th data bit time, to generate and store in said storage means n Hamming codes, each m bits long, during the data field transmission time, and

a multiplexer for coupling said data field from said circuit input to said circuit output, and thereafter, for coupling said Hamming codes from said storage means output to said circuit output.

2. The circuit of claim 1 wherein said storage means are shift registers.

3. The circuit of claim 2 further comprising:

a parity shift register n bits long,

a parity exclusive OR gate, the output of which is coupled to the serial input of said parity shift register, the serial output of said parity shift register coupled to one input of said parity OR gate, and the other input of said parity OR gate coupled to said circuit input, and

wherein said multiplexer also couples the parity shift register contents to said circuit output.

4. A circuit which can be used either for generating n Hamming codes each m bits long during the transmission of data or for the comparison of Hamming codes to create Hamming code syndrome words comprising:

means for receiving serial binary data or Hamming codes,

m shift registers, each n bits long,

an exclusive OR gate for each shift register, the output of each exclusive OR gate coupled to the serial input of each shift register, the serial output of each shift register coupled to one input of its associated exclusive OR gate, and the other input of said exclusive OR gate coupled to said means for receiving,

a multiplexer for outputting said binary data received by said means for receiving or for outputting the contents of said shift registers, and

control means for enabling said exclusive OR gates in binary count order to generate Hamming codes in said shift registers, or to enable said exclusive OR gates sequentially, as an input set of Hamming codes is being received, to compare the codes being received to the codes stored in shift registers to generate Hamming code syndrome words at the output of said OR gates for temporary storage in said shift registers.

5. The circuit of claim 4 further including:

a parity shift register n bits long,

a parity exclusive OR gate, the output coupled to the serial input of said parity shift register, the serial output of said parity shift register coupled to one input of said parity exclusive OR gate, and the other input of said parity exclusive OR gate coupled to said circuit input, and

wherein said multiplexer couples the parity shift register contents to said output.

6. The circuit of claim 5 further comprising:

means coupled to said multiplexer for storing a syndrome word which specifies the location in said data of an error burst, and

means coupled to said parity register for storing the contents of said parity register, said contents comprising a bit map of the bits in error.

7. The method of using Hamming codes to correct an n bit error burst in a serial data field a maximum of 2^m n bits long comprising the steps of

generating two sets of n Hamming codes, one during the transmission and one during the reception of said data, each code word m bits long and each code word associated with a 2^m bit word where every n^th bit in the data field comprises a data word,

generating two n bit parity words, one during the transmission and one during the reception of said data, where each parity bit is the parity of each word,

comparing said two sets of Hamming codes to determine syndrome words to determine the location of said error burst in said data stream,

comparing the parity words to generate an error burst bit map, and

correcting the errors in parallel by exclusive ORing the bit map with the data in the locations specified by said syndrome words.

8. The method of generating Hamming codes for correcting an n bit error burst in a data stream 2^m n bits long comprising the steps of:

initializing m words of memory, each n bits long,

exclusive ORing the contents of the first n bits of data with the contents of the first word of memory,

continuing to exclusive OR the incoming n bit data words with the contents of the memory word locations in binary count order, so that, after the entire data stream has been transmitted, said m words of memory will contain n Hamming code words, each m bits long, one bit of each Hamming code word in each memory word location.

9. The method of generating a first set of Hamming codes during a first transmission of data and the subsequent comparing of a second set of Hamming codes generated during a second transmission of said data to said first set, comprising the steps of:

using the steps of claim 8 to generate a first set of Hamming codes during the first transmission of data,

temporarily storing said first set of Hamming codes,

using the steps of claim 8 to generate a second set of Hamming codes during the second transmission of data, and

exclusive ORing the first and second sets of Hamming codes to produce syndrome words.

10. The method of correcting an n bit error burst in a transmitted and received data stream containing n words, each 2^m bits long where each word comprises every n^th bit of said data stream, comprising the steps of:

determining the parity of each 2^m bit word of transmitted data,

using the method of claim 8 to generate a first set of Hamming code words from said transmitted data, determining the parity of each 2^m bit word of received data,

using the method of claim 8 to generate a second set of Hamming code words from said received data,

exclusive ORing the first and second sets of Hamming codes thus produced to produce syndrome words to indicate the location in the data stream of said error burst,

exclusive ORing the parity of each 2^m bit word of transmitted and received data to produce a bit mark of the error burst, and

using the bit mask and error location thus determined to correct the error bits in parallel.