PDA

View Full Version : 8 bit Digital Readout



zermatten
02-10-2011, 09:02 PM
http://lbp.me/v/xnem8x

A digital readout that takes an 8-bit number in and displays it in full human-readable decimal glory. Like your calculator screen.

I've been working a lot with binary adders and the like, but I needed some way to display the binary number to an ordinary player, so I went on the path of building a display driver. It turned out to be a hell of a lot harder than I anticipated, so when I finally had it right, I decided to share, to save anyone else the same hassle.

Not sure if something similar is out there, but here's mine anyway.
linky (http://lbp.me/v/xnem8x)
It will do numbers 0 through 255. The level contains a brief description and a random number generator to demonstrate it.

Method
The display takes in binary input and converts it to binary coded decimal using the double dabble method (http://en.wikipedia.org/wiki/Double_dabble). The binary coded decimal is then passed in nibbles and decoded into a 0 through 9 output to light up each seven segment display correctly.
http://ie.lbp.me/img/ft/d0e9d99f31769b7b23002a31c4856e04e655b5b0.jpg
Image shows the double dabble method being applied, the placement of the C chips applies the shifting and each C chip adds 3 if the number coming in is greater than 5.

Conclusions
The 8 bit version is solid, fast and uses about half a small increment of thermometer per display and is entirely digital, using no lookup tables or ROM methods.

zermatten
02-11-2011, 06:43 PM
20 Bit attempt

A separate post to keep things tidy.

I have made a 20 bit version of the same display method available through a level link in the 8 bit level above. It does not however work nearly as well.

In play mode, it can display a binary number up to 1 048 575, and it does this flawlessly (I think). The issue comes in the method of applying the double dabble method over 20 iterations, as the number of calculations per iteration increases with each step. Thus the 20 bit version takes up close to 6 thermometer increments and causes temporary game engine freezes when moving, placing or (heaven forbid) copying the object.

http://ia.lbp.me/img/ft/daadb0c213bd0ca19042d74926341f44a1db7f61.jpg
The reason for the waste of resources.

Spikehead777
02-12-2011, 10:35 AM
Nice, very nice. I like it. in fact, I needed something like this the other day... well, not the display part, but some kind of converter that would take in a number of binary digits and would convert them into a form much closer to our decimal system. I hope you don't mind me reverse engineering this and learning from this so I could construct my own 16-bit version of this, as well as signed 8- and 16-bit versions as well.

However, I do have a question about this. When you take an 8-bit integer and convert it into a binary coded decimal (BCD) form, how do you only have 10 wires leading out of your chip? A single decimal digit encoded in a BCD format requires 4-bits. An 8-bit number can represent a maximum unsigned integer of 255, which has 3 digits. Now then, there are 3 digits and each digit requires 4-bits with BCD encoding. That's 12 bits.

zermatten
02-12-2011, 11:36 AM
Feel free to reverse engineer it as you will, if you get stuck with anything just ask. Also I'd like to see if your 16 bit version is viable, since the method really fills up the thermometer as you go up in bits. I didn't make a signed version, but I figured it would just be one unprocessed bit that stores the negative as 1 positive as 0 and goes straight to the negative sign display LED, might be more complicated depending how you want to implement it.

As for why you can output 255 in BCD using only 10 bits, the hundreds can only ever be 0, 1 or 2. So you really don't need to include more than 2 bits to display it, you can if you want to but the higher order bits will always be zero. In my 20 bit version I think I included all 4 bits, where only one was actually needed.

Edit:
If you cut the 20 bit version off 4 steps early you should have a 16 bit converter. just delete the last 4 rows (I think) out of the picture in my second post and it should be done.

Spikehead777
02-12-2011, 06:25 PM
Well, I'll have to build and test out the 16-bit method sometime later on. It would be interesting to see how well it would work. As for the signed stuff, you shouldn't need to have a second converter. It seems possible that both positive and negative numbers can be fed into the same converter without too much extra work (flip the sign of all bits of a negative number and add 1 to it).

Wow. Last night I didn't realize that only 2 bits were required for the final digit of an 8-bit number. I guess you shouldn't try to work with digital logic at 4 AM in the morning. =P I think just to be organized, I'll put two dummy wires/outputs in. It would seem awkward to me trying to plug 10 bits into 3 4-bit 7-segment display devices.

Aya042
02-12-2011, 06:48 PM
Also I'd like to see if your 16 bit version is viable, since the method really fills up the thermometer as you go up in bits.

Having looked at your implementation, the Add-3 Module could use some optimization, as you need to use quite a few of them with the double-dabble method.

I had a quick go combining a 4-bit BCD decoder (factoring out the unused zero case: 4 NOT gates and 9 four-input AND gates) with a simple truth-table implementation of an Add-3 encoder (4 OR gates of varying input sizes). Ten copies of your 8-bit binary to BCD uses 5.8 notches of thermo, and ten copies of mine uses only 1.8 notches. I could probably even optimize it further, but I'm not sure it's worth it.

zermatten
02-12-2011, 10:47 PM
Having looked at your implementation, the Add-3 Module could use some optimization, as you need to use quite a few of them with the double-dabble method..

Could not agree more, I built it as a first pass solution without much thought to optimization since I only planned on using an 8 bit version once myself, I was more interested in the solution than the efficiency. Would love to see how you and other people manage to optimize it, once I've had a go at getting it as condensed as I can myself.

This has been my first attempt at any sort of binary logic, so I'm sure my initial approach is rather cumbersome.

Spikehead777
02-13-2011, 07:32 AM
So, I managed to quickly build an 8-bit binary to BCD decoder based off of your method. It sucked when it came time to test it. The first issue I had was with the counter I used. I built my own up/down synchronous counter based on schematics here (http://www.allaboutcircuits.com/vol_4/chpt_11/3.html). However, when I saved it, I accidentally deleted that newest version so I ended up having an outdated counter. I had to rebuild the counter again. Then I had issues with my own BCD to seven segment display converter. Well, the issues I had there were rather easy to fix; I ended up wiring things up wrong. (Make sure you grab the right output before you wire it up to the 7 OR gates. XD) The last issue, I actually blame the game engine. I built some 4-bit, 8-bit, and 16-bit unsigned adders. However, when I used them, they didn't work at all. When I went into each adder, everything was wired up correctly... or so I thought. I had to open up each individual 1-bit full adder to refresh the wiring and see the true connections. Apparently they were all messed up. ._. So then I fixed up all the wiring for that. Then, things started working.

So anyways, after a long journey of glitches, bugs, and mistakes, I think I know of a few optimizations you can do. First, in each of your "add 3 and shift" chips, you can safely get rid of the "Less than 10" chip, the four AND gates, and the multiplexer. You'll be left with the "Greater than or equal to 5" chip and the "Add 3" chip. Feed the output from the ≥ 5 chip into the +3 chip. That new input replaces the battery in there. Already, that's a lot of gates removed from one chip. Now if you removed the same gates from all of the same modules? That should be a large improvement. As for the BCD to seven segment display converters... well, I must say your demultiplexer for that is much more cleaner than the general-purpose 4-bit demuxer that I have. =P

I wouldn't consider myself an expert at digital logic, so I'm sure someone can come up with better optimizations that what I have said, though it's a start.

Edit: Looks like someone got in an optimization of sorts already. =P Anyways, I built and tested out a 16-bit BCD convertor. It's feasible. Just the 16-bit BCD convertor by itself though fills up about 1.9 bars of free space. However, when you add in the 5 seven segment displays required to display a 16-bit number, as well as a 16-bit register, it all uses about 2.4 bars of free space.

Aya042
02-13-2011, 08:38 AM
Could not agree more, I built it as a first pass solution without much thought to optimization since I only planned on using an 8 bit version once myself, I was more interested in the solution than the efficiency.

In actuality yours does have the virtue of being easier to understand. As I mentioned in this thread (http://www.lbpcentral.com/forums/showthread.php?48996-MC-optimization-functionality-vs-readability), it's better to start out making it easy to understand as a priority, and only optimize if necessary. For an 8-bit solution yours works fine, but should you need to extend it to cover 16 or 32 (or more) bits, then optimization may become a necessity.

Point is, though, if you don't need more than 8 bits, then there's not much point in optimizing, as you can end up wasting a lot of time which would be better spent on some other aspect of its application.



Would love to see how you and other people manage to optimize it, once I've had a go at getting it as condensed as I can myself.

I have a ton of logic bits and whatnots with a number of practical applications I was planning to publish at some point, I just haven't gotten around to it yet. As with my Garden of Goodies level, the time-consuming part is not the building of the prizes, but in trying to make it clear what the practical applications are, in such a way as can be easily understood by people who have relatively little experience with the concepts.



I wouldn't consider myself an expert at digital logic, so I'm sure someone can come up with better optimizations that what I have said, though it's a start.

It was kind of annoying that I couldn't seem to find a minimal circuit schematic for the Add-3 Module anywhere on the internet, so I had to resort to the techniques I'd been taught in an electronics course nearly 20 years ago. Given the following truth table...

http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bcd03.png

...one of the simplest ways to implement such a thing is to first use a binary decoder which takes the 4 inputs (A0 thru A3), and activates one of 16 outputs for each possible combination of inputs. Arguably 16 outputs is unnecessary in this instance due to the "don't care" states (marked with an X), but I'd already built one for my binary to 7-segment decoder which did use all 16, as it displays the letters A to F for input values 10 to 15.

Then for each of the required outputs (S0 thru S3), just use a single OR gate for each one, and for each row in the truth table where that output is a 1, feed in the corresponding wire from the 16 intermediate outputs. As a further optimization, for truth tables where there are more 1s than 0s (as in the case of a 7-segment decoder), use a NOR gate instead, and feed in the inputs where the output should be 0.

This method is a reasonable trade-off between performance and implementation time. If that's not optimal enough, then you're looking at a crunching boolean algebra, akin to my (somewhat simplified) example from a previous post (http://www.lbpcentral.com/forums/showthread.php?32539-Logic-Tutoring&p=569761&viewfull=1#post569761)...


For more complicated examples, it might help to build a truth table...

ABCQ
0000
0011
0100
0110
1001
1011
1100
1110


...at which point you can create a sum of products expression for every row where Q=1...

Q = (!A !B C) + (A !B !C) + (A !B C)

From this, I can see that I need three three-input AND gates, whose outputs feed into a three-input OR gate.

Alternatively, the expression can first be simplified (http://www.allaboutcircuits.com/vol_4/chpt_7/5.html) using factorization and other principles of boolean algebra (this is kinda heavy)...

Q = (!A !B C) + (A !B !C) + (A !B C)
Q = !B ((!A C) + (A !C) + (A C))
Q = !B ((!A C) + (A (!C + C)))
Q = !B ((!A C) + A)
Q = !B (A + C)

From this, I can now implement the same logic function using one two-input OR gate, and one two-input AND gate, meaning instead of 12 connectors, I now only need 4, or probably only 3 if you also use implied logic (http://www.lbpcentral.com/forums/entry.php?881-Waste-Not-Want-Not-Part-3).

...but, TBH, I'd recommend avoiding this if you can, as it can be very complicated and time-consuming. :)

Spikehead777
02-13-2011, 09:59 AM
Oh wow. Aya042, thank you for posting that. That is definitely going to help me a lot more with logic in general.


This method is a reasonable trade-off between performance and implementation time. If that's not optimal enough, then you're looking at a crunching boolean algebra, akin to my (somewhat simplified) example from a previous post (http://www.lbpcentral.com/forums/showthread.php?32539-Logic-Tutoring&p=569761&viewfull=1#post569761)...

...but, TBH, I'd recommend avoiding this if you can, as it can be very complicated and time-consuming. :)

I enjoy doing mathematics. =P I'm a programmer (even if my main language is GML--Game Maker Language XD), so I'm supposed to be good at math and logic. Anyways, that relationship between truth tables and boolean algebra really helps a lot. It really beats trial and error, trying to guess what kind of result should do what.

tetsujin
02-23-2011, 06:13 AM
There's a bug in your decimal-to-7-segment decoder: a "6" displays as an "8". The upper right segment lights if the input is "not 5" - it should be "not 5 or 6", of course...

Cool stuff - I hadn't heard of double dabble before, so it's cool to see how it works...

Tygers
02-25-2011, 12:48 PM
I implemented this myself a few weeks ago without knowing what it was called. I just found a diagram of how to apply it.

Like Aya, I also looked for a minimal implementation and, failing to find that, created a truth table and implemented it based on that. My implementation was based on punching the truth table into http://courseware.ee.calpoly.edu/~rsandige/KarnaughExplorer.html and creating the resulting series of AND, OR and NOTs, with a few simple optimizations. The result is 7 AND gates, 4 OR gates, 2 NOR gates and 2 NOT gates. When I plugged this into the 20 bit display, it dropped the thermo use down to just the bulb.

I HIGHLY recommend the karnaugh map explorer applet for producing a desired output. It's quick at transforming a truth table into a logical function that can be easily mapped to logic gates.

Aya, I would be interested in your 7 segment hex display. I think I accidentally deleted the one I made and I don't have my notes from the logic diagram I made for it.

Aya042
02-26-2011, 01:56 PM
I HIGHLY recommend the karnaugh map explorer applet for producing a desired output. It's quick at transforming a truth table into a logical function that can be easily mapped to logic gates.

Nice. As it states, though, it doesn't always produce the minimal function, so additional factorization may still yield lower thermo use.

Additionally, for circuits which have multiple outputs based on the same set of inputs, there are almost always instances where intermediate values for one output can be reused for another output. One of the most common instances is simply the NOT of each input value which are often shared between multiple functions.



Aya, I would be interested in your 7 segment hex display. I think I accidentally deleted the one I made and I don't have my notes from the logic diagram I made for it.

I implemented it pretty much as I described above, with a 4-bit binary decoder (4 NOT gates, and 16 four-input AND gates), and a simple encoder circuit, comprising 7 NOR gates of varying input sizes (one for each of the 7 outputs), hooking in the decoder outputs where-ever the encoder outputs should be zero.

However, I suspect you could come up with a better version were you to crunch the boolean algebra, or use this applet to do it for you. :)

Spikehead777
02-26-2011, 03:22 PM
If it helps any, you can probably use www.wolframalpha.com to calculate minimal forms of boolean algebraic functions for you. Granted, I haven't had any luck generating a more efficient circuit than the current greater than 5 and 4-bit adder approach (23 gates!). On the same token, I had similar luck with the karnaugh map explorer that was posted up above.

Yeah, I still have much to learn. XD

I do have an idea for a possible optimization though. You can get use pre-fabricated holograms shaped as or stickered with numbers. Then the 4-bit decoder drives the holograms directly without having 7 extra OR gates. However, you do have 3 more holograms this way. I'd rather the 3 extra holograms though without the 7 extra OR gates.

Tygers
02-28-2011, 08:11 AM
So far this is the most efficient 3-adder I've been able to come up with. The approach I took on this was sort of a midway between using karnaugh maps and the algorithm. Basically, I made 3 observations about the 3-adder logic table.

1. The high bit output is identical to the >=5 check. So I did the >= 5 check in 3 gates and passed it directly out for the high bit.
2. The low bit output switches around when the >=5 check is true, so I just used XOR there.
3. For the middle 2 bits, I ran NOT >= 5 through an AND gate to pass the output, then used the karnaugh map explorer to figure out the cases of 5-9, with the rest marked don't care. Then I applied some simple optimization (Noting that the second lowest bit was just not XOR, for example) and this is what I got out.

http://ia.lbp.me/img/ft/c2a97f253eba3c115986d27a601df6c7cc7ded65.jpg

That powers this beast, which uses just under 2 thermo segments. (For those keeping score, that's a 33 bit display.)

http://i6.lbp.me/img/ft/b263e554a1e2b6c08d4adb32260d070bf9c86888.jpg