Hamming-Distance

Sequential Hamming Distance counter using VHDL.

Authors:
Eduardo Robson Cardoso Guedes Filho

José de Deus e Silva Neto

Introduction

In this lab, we aim to implement the calculation of the Hamming distance for two 8-bit binary words on a BASYS 3 FPGA board using the Xilinx XC7A35T-ICPG236C chip. The result is displayed both in binary using the LEDs and in decimal using 7-segment displays. The design constraint is that the result must remain visible until the user restarts the system.

Theoretical Preparation

The circuit has inputs d1 and d2 (the 8-bit words to compare), the clock signal clk, and a start signal start. Its outputs are dh (the Hamming distance, represented as a 4-bit binary word) and ready (indicating when the machine is not operating).

We start by describing the ASM (Algorithmic State Machine) and datapath, where i is a counter. Essentially, the machine compares each bit of the two words and increments dh until the sequence is finished.

Figure 1 – ASM with datapathn

After syntesis, the implementation of an ASM can be seen as a control machine which manages a series of classical components, such as registers, adders and multiplexers.

Figure 2 – Control state machine

Knowing the number of states in the control section, the number of flip-flops can be calculated as FF ⌈log2 S⌉ where S is the number of states.

• FF_control = ⌈log2 3⌉ = 2
• Operational part bits:
  • ready = 1 bit
  • a and b = 8 bits each
  • dh = 4 bits
  • i = 4 bits

Total operational flip-flops: FF_operational = 25
Total machine flip-flops: FF_total = 27.

The machine computes each bit in two clock cycles; after loading data with start = 1, the ready signal is asserted only after 16 clock cycles.

VHDL Code

The Hamming circuit does not directly control the 7-segment displays, so hamming_to_display is implemented to connect the project to the display control code.

Figure 3 – Hamming with display

Test examples:

1. d1 = 00000000 and d2 = 00000000 → dh = 0
2. d1 = 11111111 and d2 = 00000000 → dh = 8

Figure 4 – Testbench Results

BASYS 3 Board

Three tests were performed:

1. d1 = 00010001, d2 = 00011010 → dh10 = 3 (decimal display), dh2 = 0011 (binary LEDs)

Figure 5 – Basys dh=3
2. d1 = 01000110, d2 = 00100000 → dh = 4

Figure 6 – Basys dh=4
3. d1 = 01101111, d2 = 00000000 → dh = 7

Figure 6 – Basys dh=7