Can anyone me in calculating the checksum for the following
sequence:
1110011001100110
1101010101010101

Thank you.

Using which algorithm?

1110011001100110
1101010101010101
----------------------------
1011101110111011

martinmk's post is incorrect. It simply sums the two 16-bit words.

Oops if I read the title earlier I would have seen that you were
talking about UDP.

UDP's checksum uses the 16-bit one's complement of the one's
complement sum.

In other words, all 16-bit words are summed together using one's
complement:

1110011001100110 and 1101010101010101 (original 16-bit words)

The one's complement of these are:

0001100110011001 and 0010101010101010

Now sum these:

0001100110011001
0010101010101010
----------------------------
0100010001000011 (disregard any carry out of the 16 bits, in this case
there isn't any)

The sum is then one's complemented:

1011101110111100 (This would placed in the checksum field.)

FYI: the checksum that UDP performs is not only done on the UDP header
and data but is a little more complex, see RFC 768 for complete
details.

In article <1175609409.840388.295420@e65g2000hsc.googlegroups .com>, "Brad" <bradmbreer@gmail.com> writes:
> martinmk's post is incorrect. It simply sums the two 16-bit words.
>
> Oops if I read the title earlier I would have seen that you were
> talking about UDP.
>
> UDP's checksum uses the 16-bit one's complement of the one's
> complement sum.
>
> In other words, all 16-bit words are summed together using one's
> complement:
>
> 1110011001100110 and 1101010101010101 (original 16-bit words)
>
> The one's complement of these are:
>
> 0001100110011001 and 0010101010101010

NO! That completely misunderstands one's complement arithmetic.

The proposed algorithm is incorrect.

[Briefly, that proposed algorithm was a+b = ~(~a+~b) ignoring carry]

Example using incorrect algorithm:

01 + 01 = ~(10 + 10) = ~00 = 11. *WRONG*

The one's complement sum of 01 + 01 is, in fact, 10. The carry matters.


Deep background...

The name "one's complement" arithmetic derives from the way that it
supports signed quantities. The encoding of a negative number
is the bit-by-bit "one's complement" of the encoding of the
corresponding positive number.

The encoding of +1 in sixteen bit one's complement is 0000000000000001
The encoding of -1 in sixteen bit one's complement is 1111111111111110

You may notice that zero has two encodings. All ones and all zeroes.


In order to add two signed numbers encoded in one's complement format,
the requisite algorithm is:

"Add the two numbers as ordinary unsigned binary numbers"
"If there is a carry, increment the result using ordinary unsigned addition"

Let's try it.

-1 1111111111111110
+ +1 0000000000000001
---- ----------------
0 1111111111111111

Yes. It works. Remember that all one's is an encoding of zero.

[It turns out that the all zeroes form will never appear as the result
of an addition operation unless both addends were zero]


-1 1111111111111110
+ +2 0000000000000010
---- -----------------
1 (1)0000000000000000
0000000000000001 (add the carry back in)
-----------------
1 0000000000000001

Yes. It works.

-2 1111111111111101
+ +1 0000000000000001
---- ----------------
-1 1111111111111110

Yes. It works.


Now back to the context at hand -- UDP checksum computation...

The use of one's complement format to represent signed quantities
was never very common. And using a flavor of signed arithmetic to
do a checksum computation doesn't make a whole lot of sense at first
glance. So why would someone choose "one's complement" for a checksum
algorithm?

For at least three good reasons.

1. The sixteen one's complement code space only uses 65535 codes.
That leaves one unused code to represent "no checksum computed".

2. It turns out that the one's complement addition algorithm is
endian-neutral. If you are on a little-endian machine
you can add up a column of big-endian ones-complement numbers by
pretending that they are little-endian ones-complement numbers.

The answer the little-endian machine computes will be bit-for-bit
identical to the answer a big-endian machine computes.

3. Computation of the checksum can be further accelerated on machines
with word lengths greater than 16 bits.


Now, back to the example...

> 1110011001100110 and
> 1101010101010101 (original 16-bit words)
------------------
(1)1011101110111011 (unsigned binary sum)
0000000000000001 (adding carry back in)
-------------------
1011101110111100 (ones complement sum)
-------------------
0100010001000011 (ones complement of ones complement sum)


Demonstration that little-endian arithmetic gets the same result...

0110011011100110 (first addend byte-flipped)
0101010111010101 (second addend byte-flipped)
-------------------
(0)1011110010111011 (unsigned binary sum)
0000000000000000 (no carry to add in)
-------------------
1011110010111011 (ones complement sum)
-------------------
0100001101000100 (ones complement of ones complement sum

0100010001000011 (byte-flipped back to big-endian)
> 0100010001000011 (earlier result cut-and-pasted for comparison)

UDP checksum is very simple. Just use binary sum over 16-bit words and
then the result should be inverted. Disregard any carry out bit. In
your particular example the sum is:

1110011001100110
+ 1101010101010101
----------------------------
16-bit sum (NO carry) 1011101110111011
one's complemented: 0100010001000100

What UDP puts in its header in checksum field is: 0100010001000100.


My first reply was incomplete so apologize for that. You will be fine
with your homework or midterm. For further reading you may refer to:
http://www-net.cs.umass.edu/kurose/transport/UDP.html

In article <1175690380.000536.27630@e65g2000hsc.googlegroups. com>, "martinmk" <mgeorgievski@gmail.com> writes:
> UDP checksum is very simple. Just use binary sum over 16-bit words and
> then the result should be inverted. Disregard any carry out bit. In
> your particular example the sum is:

Absolutely false.

On Apr 4, 10:57 am, bri...@encompasserve.org wrote:
> In article <1175690380.000536.27...@e65g2000hsc.googlegroups. com>, "martinmk" <mgeorgiev...@gmail.com> writes:
>
> > UDP checksum is very simple. Just use binary sum over 16-bit words and
> > then the result should be inverted. Disregard any carry out bit. In
> > your particular example the sum is:
>
> Absolutely false.



Usually I do not answer on any provocation but what bothers me the
most is when you have debate without arguments. World known computer
networking authors/gurus such as James Kurose, Keith Ross and Richard
Stevens have written and explained how UDP checksum works. On the
contrary we have bri...@encompasserve.org who denied their work and
comes up with his/hers RFC on UDP checksum. Proliferating thesis
without facts definitely is a characteristic of a person full of
inferiority complexes.