Motivation. There is a fast approximation to conventional multiplication. It conceptually works like long multiplication except for the fact that the carry is discarded instead of applied to the more significant position. Hence its name: carry-less product. One use is to improve the speed of applications doing block cipher encryption in Galois/Counter Mode. The operation is also known as an XOR multiplication, as carry-discarding addition is equivalent to an exclusive or.
This question is about the quality of this approximation in terms of Hamming distance.
Carry-less product. Assume we have two non-negative integers $a=\sum_{i}a_{i}2^{i}$ and $b=\sum_{i}b_{i}2^{i}$, with $a_i , b_i \in \{ 0 , 1\}$ denoting the bits of these numbers. Then the carry-less product of $a,b$ is defined to be $c=\sum_{i}c_{i}2^{i}$, with each bit $c_i$ computed as the XOR of products of bits from the input numbers as follows:
$$c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{i-j}.$$
Questions. In terms of $n$, what is the maximum Hamming distance of the conventional product to the carry-less product that any $n$-bit numbers can have? And what is the average Hamming distance between the conventional and the carr-less product of $n$-bit numbers?
