Encoding a binary number in BCD – binary coded decimal – is necessary to „filter out“ each decimal digit from a number represented as binary. BCD in itself is actually a really simple representation, too.

To represent a single decimal digit in a computer, you need 4 bits (2^{4} = 16, which is the smallest power of two ≥9). So in order to represent all four digits of my seven segment display I need 4 * 4 = 16 bits. The question now is: How can I convert my binary number into a BCD number? To understand that conversion let’s first look at a simple case:

I’m sure everyone is familiar with this, but let me spell it out regardless: Whenever a decimal digit is 9 and we want to increment it, it overflows. In binary a 9 would be represented by 4 bits, however a 10 would still be represented by 4 bits, meaning there is no overflow in binary. We need that overflow, otherwise we mangle two decimal digits together. The next binary overflow happens at the 15/16 increment, from 1111_{b} to 10000_{b}. We can make use of that overflow, by simply adding 6, whenever a 4-bit binary nibble is greater than 9 in decimal.

We can check this works by trying it out:

1**0**_{dec} = 1010_{bin} => 16_{dec} = 1 **0000**_{bin}

1**1**_{dec} = 1011_{bin} => 17_{dec} = 1 **0001**_{bin}

1**2**_{dec} = 1100_{bin} => 18_{dec} = 1 **0010**_{bin}

1**3**_{dec} = 1101_{bin} => 19_{dec} = 1 **0011**_{bin}

1**4**_{dec} = 1110_{bin} => 19_{dec} = 1 **0100**_{bin}

1**5**_{dec} = 1111_{bin} => 19_{dec} = 1 **0101**_{bin}

As you can see, it works. Now conceptually the simplest way to convert from binary to BCD is to count up directly in BCD, while counting the binary input down to zero. Each BCD counter digit simply takes the overflow from the previous digit (or 1 in the case of the lowest digit) and adds that to its current value. If the value is equal to 9, it adds both the input and 6 to it’s value. The issue with this approach is that it can take pretty long for larger numbers.

Now the next „higher order“ of operation, i.e. a faster operation (faster meaning fewer steps needed for conversion) would be multiplication. Multiplication with a factor of 2 to be a little more precise. This is called the double-dabble algorithm. As you surely know, a division or multiplication by 2 in binary is simply a left/leftshift. That makes this algorithm a lot faster than the counting algorithm. While the counting algorithm had a runtime of O(2^{n}), this algorithm is simply O(n), with n being the number of input bits. That’s a huge improvement.

The Double-Dabble Algorithm is a fascinating little beast that can be a little tricky to understand initially. I won’t explain *how* this algorithm works, Wikipedia and other websites do a much better job at that, than I could. Instead I will focus on *why* this algorithm works. To do that I’ll take the two major questions I had when I first learned about it: „Why +3 when any BCD is larger than 4?“ And my other question: „Why is the binary MSB shifted into the BCD LSB?“

The first one is quite simple to explain. When a number is larger than 4 it will overflow into the next BCD digit if it is doubled. 5 turns into 10, 6 into 12, 7 into 14 and so on. Earlier I already explained that binary digits won’t overflow until 16, so we somehow need to get to 16+, whenever a number is 5+. We do that by adding 3. That 3 turns into a 6 after the left-shift (i.e. after being doubled).

So now we’re left with the other question, why is the MSB of the binary number shifted in first? Shouldn’t any algorithm start at the LSB so we can build our BCD digits sequentially? Well, let’s think about it: If we look at the digits of our binary number, which digit should be doubled most often, MSB or LSB? MSB obviously, it has the highest significance. Which bit will be doubled most often in our BCD registers though? The first or the last? Obviously the first! If we combine those two facts, we arrive at the conclusion that the first digit shifted into our BCD register must be the most significant digit of our binary input!

## Enough talking, let’s see some Verilog!

Alright alright, let’s start with the Verilog part of this post.

assign hexed_values[0] = i_convreg[15]; assign hexed_values[4:1] = (o_bcd[3:0] > 4) ? {o_bcd[3:0] + 4'd3} : {o_bcd[3:0]}; assign hexed_values[8:5] = (o_bcd[7:4] > 4) ? {o_bcd[7:4] + 4'd3} : {o_bcd[7:4]}; assign hexed_values[12:9] = (o_bcd[11:8] > 4) ? {o_bcd[11:8] + 4'd3} : {o_bcd[11:8]}; assign hexed_values[16:13] = (o_bcd[15:12] > 4) ? {o_bcd[15:12] + 4'd3} : {o_bcd[15:12]};

Here, that’s the interesting part. Happy now? No? Alright, let me explain then. `hexed_values`

is a register that always contains 2 things: The next bit to be shifted into the BCD register and the previous value of the BCD register. There’s one caveat though: If the previous BCD register value for any nibble was >4, that value isn’t used. Instead that value +3 is used inside `hexed_values`

. Then, on each rising clock edge, `hexed_values`

is put into `o_bcd`

. The left shift is actually hidden in the assignment above.

That’s all there is to this algorithm. The rest is some control logic to check when the conversion is done (i.e. after all 16 bits were shiftd from i_bin to o_bcd), and some reset logic.

To get to the seven segment there is actually one last step to do. A BCD to seven segment decoder. I won’t implement that though, because I can reuse something else. You might remember from the last post that the display will have a hexadecimal-mode. Each hex digit takes 4 bit, the same number of bits as a BCD digit. Moreover, each value from 0-9 has the same binary representation in both hex and BCD. This means I can simply use the hex mode to display decimal numbers by using the properties of BCD and hex. Getting from hex to seven segment representation is trivial then: It’s a simple lookup table of active segments for each of the 16 states that a 4-bit nibble can represent.

Now let’s test the encoder by attempting to decode 218_{dec} from a binary representation to BCD.

Perfect, it all works as expected. To display the BCD digits, I used GTKWave’s hex display mode – just like my display module would.

As always, here’s the full code:

module bcd_encoder ( input i_clk, i_rst, input i_begin_conv, input [15:0] i_binary, output reg o_conv_done, output reg [15:0] o_bcd ); reg [4:0] conv_ctr; reg [15:0] i_convreg; // hexed_values always contains the correct bits for the next left shift // Notably, any time a BCD digit should overflow in the next shift (i.e. whenever // any bcd digit is > 4), +3 will be added. This ensures correct overflow // into the next bcd digit, while maintaining the correct value for the // overflowing digit. wire [16:0] hexed_values; // the first digit of hexed_values is always the MSB of the input // the remaining 16 digits contain the correctly modified output data but still without the shifting assign hexed_values[0] = i_convreg[15]; assign hexed_values[4:1] = (o_bcd[3:0] > 4) ? {o_bcd[3:0] + 4'd3} : {o_bcd[3:0]}; assign hexed_values[8:5] = (o_bcd[7:4] > 4) ? {o_bcd[7:4] + 4'd3} : {o_bcd[7:4]}; assign hexed_values[12:9] = (o_bcd[11:8] > 4) ? {o_bcd[11:8] + 4'd3} : {o_bcd[11:8]}; assign hexed_values[16:13] = (o_bcd[15:12] > 4) ? {o_bcd[15:12] + 4'd3} : {o_bcd[15:12]}; always_ff @(posedge i_clk) begin if(i_rst) begin o_conv_done <= 1; o_bcd <= 16'b0; i_convreg <= 16'b0; conv_ctr <= 0; end else begin if(conv_ctr == 0 && i_begin_conv && o_conv_done) begin // start of conversion // store i_binary in internal register and begin converting it i_convreg <= i_binary; o_conv_done <= 0; o_bcd <= 16'b0; end else if (!o_conv_done && conv_ctr < 16) begin // conversion has started, but isn't completed, increment bit counter conv_ctr <= conv_ctr + 1; // values are shifted from i_convreg to output in o_bcd_digits i_convreg[15:0] = {i_convreg[14:0], 1'b0}; // o_bcd always contains current state of conversion // here the shift is introduced o_bcd[15:0] <= hexed_values[15:0]; if(conv_ctr == 15) begin o_conv_done <= 1; end end end end endmodule