ハミング距離を計算する回路を設計する？

Question

私はこの質問に出くわしました。私は教科書やインターネットでそれを見つけることができませんでした。かなり独特のようだ。

私は、コンパレータと加算器がいくつか関わっていると思いますが、どこから始めればいいのか分かりません。

Answer 1

最初のステップは間違いなく2つのビットセットを排他的論理和することです。次に、出力の論理1の数を数える必要があります。あなたの回路を設計するための最良の方法は、this questionで論じられたハックの完全な類推を行い、nneonneoによってそのanswerで完全に説明されることです。これは、順次計数に頼るのではなく、最適な加算器のツリーをもたらす。アイデアは、各レイヤーで、入力のサブセットの最大可能な総和をキャップする方法と、それが適合するビット数をキャリービットの必要性を排除する方法を知っているということです。プログラミング手法は32ビット用に設計されていますが、それよりも少なくても簡単に変更可能です。

ハミングウェイトを計算するためのより多くのアルゴリズムについては、this linkを参照してください。