Checksum calculation unit and method for error detection on data packets

• US 5,500,864 A
• Filed: 06/14/1993
• Issued: 03/19/1996
• Est. Priority Date: 08/29/1990
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Hoff, James F., Gonia, Patrick S.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): CHUNG, PHUNG M
• Application Number:
  US08/076,827
• Time in Patent Office: 1,009 Days
• Field of Search: 371/37.5, 371/40.1, 371/48, 371/53, 364/778, 364/779, 364/780, 364/781, 364/782, 364/783, 364/784, 364/785
• US Class Current: 714/807
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

A high performance transport layer checksum calculation unit and method is described for use in computer data communications systems which provides simultaneous general purpose data movement and checksum calculations. Data must be copied from the main memory of a computer in order to be transmitted and often a checksum must be calculated on the data for error detection purposes. The invention involves performing both of these tasks simultaneously thus requiring only one scan of the data memory. The checksum calculation method improves throughput capacity via a unique hardware architecture supporting delayed checksumming of packet segments. A net improvement for packets larger than a certain size is achieved via partial addition during DMA controlled memory access allowing improved average cycle time per data packet segment.

Claims

1. A data communication system interactive so as to facilitate a flow of data between at least a main memory and network memory, said data communication system comprising:

an adder unit having at least one partial adder for calculating checksum values and inputs,

a checksum calculating means comprises an n-bit data byte delivery means to deliver a series of n-bit data bytes (which is called "checksum calculation results"), derived from input data, to the inputs of said adder unit, and a first direct memory accessing address generator connected to the main memory and a second direct memory accessing address generator connected to the network memory to move data in a form of data packets, each data packet having a first plurality of bytes which specify protocol information, a second plurality of bytes which specify checksum information and a third plurality of bytes which specify a block of data, to flow in one of either of two directions;

from the network memory to main memory and simultaneously to checksum calculating means, or

alternatively, from main memory to network memory and simultaneously to said checksum calculating means; and

means of calculating values from the checksum calculation results and placing these values into the data packets.

2. The data communication system according to claim 1 wherein said checksum calculating means complies with a protocol checksum algorithm.

3. The data communication system according to claim 1 wherein said network memory and said main memory comprise a data memory and a control unit which directs address generators to move data to two locations simultaneously and in parallel, one of said locations being the checksum calculating means having the at least one partial adder, and the other one being selected from one of either said network memory or said main memory the direction of said selection being dependent on the direction of data flow.

4. The data communication system according to claim 1 wherein said checksum calculating means comprises three partial adders, said adders being arranged in series as adders one, two and three to receive transmitted bytes of data so that:

adder one generates a sum result iteratively, by adding the value of a currently received word with partial sum and partial carry values generated by the adder one in the previously run cycle, yielding the running sums of the transmitted bytes of data;

adder two sums the value of the partial carries from adders one, two and three from the previously run cycle; and

adder three generates a sum-of-sums result by summing the partial sum values from adders one, two, and three from the previously run cycles, yielding the successive running sum of sums of the transmitted bytes.

5. The data communication system according to claim 4 wherein said arrangement with partial sums computed in adder three and partial carries computed in adder two, provides for said sum-of-sums results to be maintained at the output of adder three after the last byte of the transmitted data is processed and a required number of summing cycles is completed.

6. The data communication system according to claim 1, said first direct memory accessing address generator includes buffer chaining means allowing multiple discontinuous blocks of data located in different sections of the main memory to be checksummed by linking separate discontinuous blocks together into a single logical group of data.

7. The data communication system according to claim 1 such that said partial adders comprise of a plurality of one-bit wide full adders, having three inputs for addition and two outputs for carry and sum values, all operating independently and said one-bit wide full adders operating in parallel allowing partial adders to add without taking into consideration the propagation of carry bits through the adder bit positions during the addend cycle.

8. A data communication system comprising:

a checksum calculation circuit, having partial arithmetic summing circuitry, which complies with a protocol checksum algorithm;

means for applying n-bit data bytes to partial arithmetic summing circuitry;

means for outputting checksum calculation results from the arithmetic summing circuitry; and

means for calculating values from the checksum calculation results and placing these values into data packets, each data packet having a first plurality of bytes which specify protocol information, a second plurality of bytes which specify checksum information and a third plurality of bytes which specify a block of data, which will be transmitted with said n-bit data bytes so that when the checksum calculation results are calculated again during reception by an identical data communication system which is linked by said data communication system to receive said data packets, a sum, and a sum of sums results will indicate whether there is an error.

9. The data communication system according to claim 8 wherein said partial arithmetic summing circuit generates a sum value by calculating a sum of bytes of said data packets and a sum-of-sums value by adding successive sums to the successive running sums.

10. The data communication system according to claim 8 wherein the arithmetic summing circuit includes three partial adders arranged in series so that a first one of said partial adders generates said sum values and all three of said partial adders operate jointly to generate said sum-of-sums values.

11. The data communication system according to claim 10 wherein said partial adders are arranged in series where the partial sums are computed in adder three and partial carries are computed in adder two so that the partial sum output of adder three produces a total sum value which equals the sum of sums of the transmitted bytes after the last byte in a packet has been processed and a number of summing cycles required to clear the carries is completed.

12. The data communication system according to claim 10 wherein each of said partial adders has inputs (A0-A7), (B0-B7), and (C0-C7) and outputs (PS) and (PC).

13. A data communication system of a type having a checksum calculation circuit, operable pursuant to a protocol for calculating sum and sum-of-sum values, comprising:

sum and sum-of-sum outputs;

first, second, and third n-bit partial adder units, each of said partial adder units having a 3 n-bit sets of added inputs (A), (B), and (C), a set of n-bit partial sum outputs (PS), and a set of n-bit partial carry outputs (PC);

means for applying an n-bit data byte to said inputs (A) of said first partial adder unit;

means for applying left shifted (PC) outputs of said first partial adder unit to said (C) inputs thereof and to said (B) inputs of said second partial adder unit;

said (PS) outputs of said first partial adder being applied to said (B) inputs thereof and to said sum output and to said (A) inputs of said third partial adder;

means for applying left shifted (PC) outputs of said second partial adder unit to said (C) inputs thereof;

said (PS) outputs of said second partial adder unit being applied to said (C) inputs of said third partial adder unit;

means for applying left shifted (PC) outputs of said third partial adder unit to said (A) inputs of said second partial adder unit; and

said (PS) outputs of said third partial adder unit being applied to said (B) inputs thereof and to said sum-of-sums output.