ระยะห่างระหว่างผลิตภัณฑ์และผลิตภัณฑ์ที่ไม่ต้องพกพา

แรงจูงใจ. มีการประมาณอย่างรวดเร็วสำหรับการคูณแบบเดิม แนวคิดนี้ทำงานเหมือนกับการคูณแบบยาว ยกเว้นความจริงที่ว่าการพกพาถูกละทิ้งแทนที่จะนำไปใช้กับตำแหน่งที่มีนัยสำคัญมากกว่า ดังนั้นชื่อของมัน: สินค้าพกพาน้อย. การใช้งานอย่างหนึ่งคือการปรับปรุงความเร็วของแอปพลิเคชันที่ทำการเข้ารหัสบล็อกการเข้ารหัส Galois/โหมดเคาน์เตอร์. การดำเนินการนี้เรียกอีกอย่างว่า การคูณ XORเนื่องจากการเพิ่มการทิ้งพกพานั้นเทียบเท่ากับการพิเศษหรือ

คำถามนี้เกี่ยวกับคุณภาพของการประมาณนี้ในแง่ของระยะแฮมมิ่ง

สินค้าพกพาน้อย สมมติว่าเรามีจำนวนเต็มที่ไม่เป็นลบสองตัว $a=\sum_{i}a_{i}2^{i}$ และ $b=\sum_{i}b_{i}2^{i}$, กับ $a_i , b_i \in \{ 0 , 1\}$ หมายถึงบิตของตัวเลขเหล่านี้ จากนั้น สินค้าพกพาน้อย ของ $a,ข$ กำหนดให้เป็น $c=\sum_{i}c_{i}2^{i}$ด้วยแต่ละบิต $c_i$ คำนวณเป็น XOR ของผลคูณของบิตจากตัวเลขที่ป้อนดังนี้

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

คำถาม. ในแง่ของ $n$สูงสุดคืออะไร ระยะแฮมมิ่ง ของผลิตภัณฑ์ทั่วไปไปจนถึงผลิตภัณฑ์พกพาน้อยว่าใดๆ $n$ตัวเลขบิตสามารถมี? และระยะแฮมมิ่งเฉลี่ยระหว่างผลิตภัณฑ์แบบธรรมดากับแบบไม่มีคาร์คือเท่าไร $n$บิตตัวเลข?