ASIC from Scratch – Part 8: Binary to BCD

Veröffentlicht von

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 (24 = 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 1111b to 10000b. 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:

10dec = 1010bin => 16dec = 1 0000bin
11dec = 1011bin => 17dec = 1 0001bin
12dec = 1100bin => 18dec = 1 0010bin
13dec = 1101bin => 19dec = 1 0011bin
14dec = 1110bin => 19dec = 1 0100bin
15dec = 1111bin => 19dec = 1 0101bin

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(2n), 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 218dec from a binary representation to BCD.

Fig. 1: Wave diagram of the binary to BCD conversion.

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

Kommentar hinterlassen

Deine E-Mail-Adresse wird nicht veröffentlicht.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.