Khoảng cách Hamming giữa sản phẩm và sản phẩm ít vận chuyển

Động lực. Có một xấp xỉ nhanh với phép nhân thông thường. Về mặt khái niệm, nó hoạt động giống như phép nhân dài, ngoại trừ thực tế là giá trị thực bị loại bỏ thay vì được áp dụng cho vị trí quan trọng hơn. Do đó tên của nó: sản phẩm ít mang theo. Một cách sử dụng là cải thiện tốc độ của các ứng dụng thực hiện mã hóa mật mã khối trong Chế độ Galois/Bộ đếm. Các hoạt động còn được gọi là một phép nhân XOR, vì bổ sung loại bỏ mang theo tương đương với độc quyền hoặc.

Câu hỏi này là về chất lượng của xấp xỉ này theo khoảng cách Hamming.

Sản phẩm không mang theo. Giả sử chúng ta có hai số nguyên không âm $a=\sum_{i}a_{i}2^{i}$ và $b=\sum_{i}b_{i}2^{i}$, với $a_i , b_i \in \{ 0 , 1\}$ biểu thị các bit của những con số này. Sau đó sản phẩm ít mang theo của $a,b$ được định nghĩa là $c=\sum_{i}c_{i}2^{i}$, với mỗi bit $c_i$ được tính là XOR của tích bit từ các số đầu vào như sau:

$$c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{i-j}.$$

câu hỏi. xét về $n$, tối đa là bao nhiêu Khoảng cách hamming của sản phẩm thông thường sang sản phẩm ít vận chuyển mà bất kỳ $n$-số bit có thể có? Và khoảng cách Hamming trung bình giữa sản phẩm thông thường và sản phẩm không có carr là bao nhiêu? $n$-bit số?