Name: Binary to BCD (Double Dabble Algorithm) - Computerphile
Uploaded: 2020-03-27T16:56:00.000Z
Duration: 12 min 53 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

In some ways there are some awkward incompatibilities between the decimal

Adverbs of degree

that we like to use and the binary which is so efficient and wonderful for computers

to use. We've seen one example of this already. I think I mentioned in a

previous video that .1, or .10, (ten cents in otrher words) in decimal, in your current bank balance is

not exactly representable as a binary number. You look at what it is in binary

0.00011001100 It just isn't, you know. It keeps on

recurring. Just as 1/3 in decimal isn't exact. It goes .333333 for ever.

Decimal and binary sometimes don't mix.  Now here's going

to be a classic example. Let's just think this through, without even writing

anything down. if we've got a 4-bit nibble,

we know that in hex it goes from 0000 to 1111,  15 represented as F [hex]. We can't use

our full range [for BCD]. This is binary-coded decimal not binary-coded hexadecimal.

Yeah?! We have got to say that the moment that representation, even in one nibble,

gets to 1010 that is 10 [decimal] you can't leave it as 1010 you've now got have

2 nibbles. The left nibble with a 1 in it and the right nibble wants to look like 0.

You can't compress it into a single nibble, say 1010 and say: "I'm sorry folks

you'll have to learn hex, because otherwise you won't understand your bank

balance!" This is not going to go down very well. The challenge then is, if you're

using a 4-bit nibble, but only for the decimal range 0-9, you've somehow

got to make - in all your bit twiddles - you've got to make it carry into another

nibble on the left at 10[decimal] and not at 16  [decimal], which is what hexadecimal will do for you.

So, how does one, sort of, bridge that gap? Probably the best way for me to get

in to the hard bit about this is [to] go straight away for that magic

number 10. Let's represent it in binary and then say: "How do we convert it into

BCD?" And realize that we need that second nibble on the left. What I'd like to do

here is to draw myself columns, and I'm going to restrict myself to things that

are, at most, 2 decimal digits. Let's remind ourselves, up here, that we're

going to have a tens nibble and a units nibble, and we'll initialize everything

to zeros. But, above here, just to keep things very simple,

we'll use 4-bit binary representations. And I hope you will all agree that 1010

is ten, in base ten. And the reason for that is that the binary - in

four bits - that's an 8, that's the 2, so that's 10. This technique which is

called Double Dabble - I don't know how it was discovered, it's fiendishly clever -

but the idea is we'd love to convert binary into BCD by, as far as possible,

using simple bit shifts all the time and doing the minimum of mucking about to

get it to carry early. So the 'Double' reflects the fact that we're going to shift

this bit-pattern across into here. And we're going to regard it as one

huge, great big, 12-bit register here. A walloping  great shift register - all joined together.

Even though I've drawn it out separately. It's just going to move from

the right across to the left. I'm going to move them across. And remember, every time you

shift the thing by one place left you are basically doubling it. OK,

that's where the 'Double' comes from. But we find we have to intervene to make it

look right at the end and that is where the 'Dabble' comes from. If you look up

'dabble', as I did in Chambers' dictionary it's one of the meanings is " ... to make a

trivial alteration to". OK to make a small alteration to something you're 'dabbling'

with it. OK, so that's where Double Dabble comes. OK, so it's basically

doubling, with a little bit of dabbling. And the truth really hits you at 10. So,

let's progressively shift this by 1 bit left. What's going to

happen first of all? You shift over that '1' bit

You push it across into here because this is a unified register, for the moment.

Prists will say: "Ah! but when you shift left, like that, you should fill in with

zeros on the right." Yes, that is what will actually happen, inside the hardware,

But I prefer not to pad with zeros, on the right, at a shift, because I want you

to see when I've finished. So, we could call this shift no. 1.  Let's do another

one. That 1 moves into that position but you're bringing over another 0

out of that part and that's leaving you with 10 in there. Now, notice what's

happened. On shift 1, here, you had a 1 on the right, in that nibble. By the time

you've shifted it left one place it's in the 2s position.

So, you've doubled it. Let's do shift no. 3 and a zero is left, So, that is

shift 3. Now, this is where we can begin to see trouble on the horizon.

We have got one more shift left to do and, if you don't do anything about it, it's

just going to end up with 1010 in here. I mean, all right, what's

happened here, look, is that was 2 - you doubled it, but because you shifted a

1 in, and not a 0, you've doubled it and added 1. That now says 5, OK?

So, basically it's doubling but sometimes if the bit you shift over is 1, and

not a 0, it's double and add 1. But essentially it's doubling. Now the

trouble is coming on the horizon because I can see that if I just push that 0

bit over here, I'm going to end up with 1010. I know, it's 10 [decimal].  Fine!

It's not representable as a digit from 0-9. So, what should you do

then? Let it happen anyway and then look at it and say: "Oh my golly, it's gone to

ten; it's gone to eleven; it's gone to fifteen even! I'd better backtrack and undo

it and then redo it ?!" No! Dive in early and reason as follows:

Concentrate everybody! OK, what we want here

is for this thing to come out looking like 0001 0000.

Because that - regarding these as BCD digits -

that's 1 0 i.e. ten. That's exactly what you want. So how do we make that happen?

How do we make it carry over into this left-hand nibble, here, when it doesn't

want to at the moment. So the fiendishly clever thing says: "Take a look at what

you've currently got because if what you got is 5 or more, the act of doubling

it is bound to get you into a number that needs to carry across [tothe next BCD nibble]. So, if it is

going to cause you trouble, at 5 or more, we wanted to carry at 10 [decimal], it

innately would like to carry at 16 and you don't want that. What's the

difference, Sean, between 10 and 16? >> Sean: 6 >> DFB: 6. what's half of that? >> Sean: 3

>> DFB: All right. So, if we add three the fact  that we're then shifting it will double our 3

contribution [to] 6, And we'll make it carry  [because we'll force that nibble past 16] So, the rule is - on Double Dabble - if

what you see in your nibble [before shifting] is  5 or more, then add 3. So, here we go, look.

Next stage now. Because we've seen trouble on the horizon. It's 5, so add

3. And 3, we agree, is 11 [binary]. Now, here you do have to do a little

addition with carries. You can't avoid it. Some carries will

have to take place. 1 and 1 is 0 (carry 1); 1 and 1 is 0(carry 1);

1 and 1 is 0 (carry 1). The act of adding 3 will make it look not like

0101 - you've added the 3, it now looks  like 1000.

Magic! But, what happens when you shift the final 0 in? That 1 will shift

left, into the left-hand nibble. And you'll end up with:

0001 0000. And this thing is now empty. So you know you've come to the

end of your conversion. It's so cool.  I love it dearly.

You could argue though, the one problem with all this is that, in order to do

your shifts quickly, you've got this [bit pattern] in a sort of a unified shift register

full of bits. Your nibbles -  in the end - end up looking correct. But you're going to have