This time I promise to talk about something more technical, so I'll cover how I designed, from scratch, the BCD (Binary Coded Decimal) to 7 segment decoders that will drive the clock display, and also the day of the month display as part of the calendar.
I had originally intended to have an n-bit ripple counter feeding a decoder that could translate that n bit value in to outputs for two 7 segment displays. It seemed like the nicest and most "pure" solution, and I had begun designing things this way, but it started to get very complex vey quickly - a lot of gates using a lot of transistors, and I started to worry that I wouldn't be able to fit all of the decoders for the clock and calendar on to a single board each, and this is something I am trying very hard to achieve (i.e. one block of functionality per board).
I'll cover ripple counters in another post, but I've opted for a solution that involves one counter per display with varying numbers of bits depending on the maximum value a display needs to show. For example, the seconds "unit" counter will be 4 bits able to count 0-15 but resetting at 10 (so, 0-9), while the "tens" counter will be 3 bits able to count 0-7 but resetting at 6 (so, 0-5). The "tens" counter for hours would be 3 bits as it only needs to show up to the 20's. As a result I had to come up with three 7 segment decoders, one to handle each of 2, 3 and 4 bit BCD values, but I'll cover the process for the 4 bit decoder in this post (it's pretty much the same for the others).
The first step was to nut out a truth table that would determine which segments will be on for each given input value, and this is what I came up with:
It also helps to have a diagram of the display next to your truth table as a reference. 7 segment displays have an industry standard layout with each segment labelled a-g, and laid out in the arrangement you see above. Also, I've opted to only decode values 0-9, ignoring values 10-15 which would otherwise (perhaps) decode to letters A-F for hexadecimal readout - in my decoder they will result in a blank display.
Through this truth table you can also "stylise" your digits. For example, some decoders may leave segment a off for the digit 6, or segment d off for digit 9, others might turn them on. It's really up to you at this point (I chose to have segment a on for 6 and d on for 9 as I like that style).
The next step is where you start to work out the logic that will drive the segments. The method I used involves k-maps. You can find more detail on these at this Wikipedia page, but I'll give a brief run through of how I worked with them here.
The best way I can think of to explain a k-map is a table with a number of cells equal to and representing the number of different values in a given sized binary number. A 4 bit binary number would have a k-map of 16 cells because 4 bits of binary can represent 16 different values (0-15). And we need one k-map per segment of a display so that each input value can be mapped against a segment to determine whether it should be on or off for that value. This gives 7 k-maps for a 7 segment display. So this is what I started with:
AB and CD represent each half of the input value, and the arrangement is done according to Gray code, which might look a little confusing at first, but actually starts to make sense after working with k-maps for a little while. Pay attention to the ordering of the input bits A-D. In the truth table they are ordered most to least significant bit, but in the k-map I've done them least to most significant bit. The ordering doesnt matter, but in the truth table I opted to represent it how you'd typically see binary, whereas in the k-map I did it for ease of recognition with the bits reading left to right.
The next step is to place a 1 in each cell of the k-map where, in this case, the a segment of the display should be turned on, and 0 where it should be off. To do this, take each value from the a column of the truth table and place it in the appropriate cells of the k-map to come up with something like this:
With the above k-map you then need to define what are called "minterms" (or "maxterms" if you're working complementary wise), and they are essentially formulas that match cells of the k-map. I'm not sure if that made much sense, but heres a couple of examples that might help make this easier to understand:
And lets see if I can try to explain how this works...
Taking the yellow example, we can see that two cells are highlighted, and the formula to match those two cells is A'B'C'. The apostrophe indicates the complement, so A' ("not A") matches on 0, whereas A would match on 1. Beginning with A', match any rows where A is 0, which is the top two rows. Next is B', so this would narrow the match to only rows where B is also 0, so this would match the top row only as in the bottom row, A is 1. And finally with C' we further narrow the match to only columns where C is 0. So in that case, we end up with the two left hand cells of the top row.
Moving to the red example, we see that we need to start by matching only rows where the value of B is a 1. Next we need to narrow the match to only columns where C is 0, and finally columns where D is 0. This results in the middle two cells of the left hand column.
I'll leave the green example for you to run over and see if you can figure out how it works (answer at the bottom of the post).
The final step in this part of the process is to work out all of the minterms for the given k-map, and this is what I came up with for the a segment:
The same process is repeated until you have mapped out all of the segments against their respective input values. I've shared a spreadsheet which contains all of the k-maps for the 2, 3 and 4 bit decoders with the minterms that I worked out that you can look over, copy, play with, and maybe you might even find some efficiencies that I could have made. I tried hard and went over them for several days to try and minimise them as much as I could, but everyone reaches a point where you think "good enough".
Some logic can also be simplified, for example, A'BD' actually matches two cells, one on either side of the map. It doesn't matter that it overlaps with BC'D', but it does save a transistor because to match a single cell you need to AND against 4 inputs. 😏
I haven't been able to properly represent instances where minterms overlap each other, for example A'B'C' and B'C'D both match the cell corresponding to value ABCD = 0001. A limitation of using a spreadsheet I suppose. But it should all be there and all be correct. Certainly I think so because ...
The final step was to translate this to logic itself, taking inputs and producing output according to the k-map. A piece of software I have been using to simulate a lot of the logic for my clock is logic.ly. It's a neat piece of software that you can also try on-line for free or download a 30 day trial for various OSes. It has so far proven to be rather valuable in testing out whether something I have come up with will actually work or not - before committing it to a mess of wires.
The minterms defined above can now be translated in to logical AND operations. For example, to match A'B'C', we simply need a 3-input NOR gate (remember, a NOR gate can be used to perform AND operations). In the case of A'B'C', if you connect non-inverted A, B and C input signals to the NOR gate, if all of those inputs are low the NOR gate output will be high. That high signal can be fed in to an OR gate (NOR followed by a NOT) to turn on the a segment when the A, B and C inputs are all low, including any other situations where it should be on.
After a little bit of analysis you might also happen to notice that some gate combinations are used several times over. In my case, CD' is used 4 times in the decoder, so I was able to build that as its own little block of logic which could be fed in to other gates. This actually saves me a further single solitary transistor. BD' is used 3 times, but with 3 transistors to implement a similar little block of logic as CD', and then 3 transistors used to accept its input in to the 3 gates that use it versus using 2 transistors in the 3 gates that use that combination, you only break even. The real savings are at 4 uses and above, but unfortunately we don't get that many opportunities in this decoder.
Anyhow, this is what I came up with for my 4 bit BCD to 7 segment decoder and, of course, using nothing but NOR and NOT gates:
As you can see, with a value of 0110 (6) being input in to the decoder, I am getting a 6 on the display.
Don't worry about trying to re-create this yourself (unless you want to try out my circuit above in the online logicly demo, which I don't believe can load files), I have also shared the logicly files for all three of the decoders: 2 bit decoder, 3 bit decoder, 4 bit decoder
The end result, including any optimisation that I could find myself, is that each decoder uses the following number of transistors and gates (inverters/NOT gates included):
I think I'll leave it there for now. A similar process was followed to determine the logic for the 16 segment displays to display 3 letter month names (JAN, FEB, MAR etc) and 2 letter day of week names (MO, TU, WE etc). I'll cover this in another post.
Answer: ACD'
I had originally intended to have an n-bit ripple counter feeding a decoder that could translate that n bit value in to outputs for two 7 segment displays. It seemed like the nicest and most "pure" solution, and I had begun designing things this way, but it started to get very complex vey quickly - a lot of gates using a lot of transistors, and I started to worry that I wouldn't be able to fit all of the decoders for the clock and calendar on to a single board each, and this is something I am trying very hard to achieve (i.e. one block of functionality per board).
I'll cover ripple counters in another post, but I've opted for a solution that involves one counter per display with varying numbers of bits depending on the maximum value a display needs to show. For example, the seconds "unit" counter will be 4 bits able to count 0-15 but resetting at 10 (so, 0-9), while the "tens" counter will be 3 bits able to count 0-7 but resetting at 6 (so, 0-5). The "tens" counter for hours would be 3 bits as it only needs to show up to the 20's. As a result I had to come up with three 7 segment decoders, one to handle each of 2, 3 and 4 bit BCD values, but I'll cover the process for the 4 bit decoder in this post (it's pretty much the same for the others).
The first step was to nut out a truth table that would determine which segments will be on for each given input value, and this is what I came up with:
It also helps to have a diagram of the display next to your truth table as a reference. 7 segment displays have an industry standard layout with each segment labelled a-g, and laid out in the arrangement you see above. Also, I've opted to only decode values 0-9, ignoring values 10-15 which would otherwise (perhaps) decode to letters A-F for hexadecimal readout - in my decoder they will result in a blank display.
Through this truth table you can also "stylise" your digits. For example, some decoders may leave segment a off for the digit 6, or segment d off for digit 9, others might turn them on. It's really up to you at this point (I chose to have segment a on for 6 and d on for 9 as I like that style).
The next step is where you start to work out the logic that will drive the segments. The method I used involves k-maps. You can find more detail on these at this Wikipedia page, but I'll give a brief run through of how I worked with them here.
The best way I can think of to explain a k-map is a table with a number of cells equal to and representing the number of different values in a given sized binary number. A 4 bit binary number would have a k-map of 16 cells because 4 bits of binary can represent 16 different values (0-15). And we need one k-map per segment of a display so that each input value can be mapped against a segment to determine whether it should be on or off for that value. This gives 7 k-maps for a 7 segment display. So this is what I started with:
AB and CD represent each half of the input value, and the arrangement is done according to Gray code, which might look a little confusing at first, but actually starts to make sense after working with k-maps for a little while. Pay attention to the ordering of the input bits A-D. In the truth table they are ordered most to least significant bit, but in the k-map I've done them least to most significant bit. The ordering doesnt matter, but in the truth table I opted to represent it how you'd typically see binary, whereas in the k-map I did it for ease of recognition with the bits reading left to right.
The next step is to place a 1 in each cell of the k-map where, in this case, the a segment of the display should be turned on, and 0 where it should be off. To do this, take each value from the a column of the truth table and place it in the appropriate cells of the k-map to come up with something like this:
With the above k-map you then need to define what are called "minterms" (or "maxterms" if you're working complementary wise), and they are essentially formulas that match cells of the k-map. I'm not sure if that made much sense, but heres a couple of examples that might help make this easier to understand:
Taking the yellow example, we can see that two cells are highlighted, and the formula to match those two cells is A'B'C'. The apostrophe indicates the complement, so A' ("not A") matches on 0, whereas A would match on 1. Beginning with A', match any rows where A is 0, which is the top two rows. Next is B', so this would narrow the match to only rows where B is also 0, so this would match the top row only as in the bottom row, A is 1. And finally with C' we further narrow the match to only columns where C is 0. So in that case, we end up with the two left hand cells of the top row.
Moving to the red example, we see that we need to start by matching only rows where the value of B is a 1. Next we need to narrow the match to only columns where C is 0, and finally columns where D is 0. This results in the middle two cells of the left hand column.
I'll leave the green example for you to run over and see if you can figure out how it works (answer at the bottom of the post).
The final step in this part of the process is to work out all of the minterms for the given k-map, and this is what I came up with for the a segment:
Some logic can also be simplified, for example, A'BD' actually matches two cells, one on either side of the map. It doesn't matter that it overlaps with BC'D', but it does save a transistor because to match a single cell you need to AND against 4 inputs. 😏
I haven't been able to properly represent instances where minterms overlap each other, for example A'B'C' and B'C'D both match the cell corresponding to value ABCD = 0001. A limitation of using a spreadsheet I suppose. But it should all be there and all be correct. Certainly I think so because ...
The final step was to translate this to logic itself, taking inputs and producing output according to the k-map. A piece of software I have been using to simulate a lot of the logic for my clock is logic.ly. It's a neat piece of software that you can also try on-line for free or download a 30 day trial for various OSes. It has so far proven to be rather valuable in testing out whether something I have come up with will actually work or not - before committing it to a mess of wires.
The minterms defined above can now be translated in to logical AND operations. For example, to match A'B'C', we simply need a 3-input NOR gate (remember, a NOR gate can be used to perform AND operations). In the case of A'B'C', if you connect non-inverted A, B and C input signals to the NOR gate, if all of those inputs are low the NOR gate output will be high. That high signal can be fed in to an OR gate (NOR followed by a NOT) to turn on the a segment when the A, B and C inputs are all low, including any other situations where it should be on.
After a little bit of analysis you might also happen to notice that some gate combinations are used several times over. In my case, CD' is used 4 times in the decoder, so I was able to build that as its own little block of logic which could be fed in to other gates. This actually saves me a further single solitary transistor. BD' is used 3 times, but with 3 transistors to implement a similar little block of logic as CD', and then 3 transistors used to accept its input in to the 3 gates that use it versus using 2 transistors in the 3 gates that use that combination, you only break even. The real savings are at 4 uses and above, but unfortunately we don't get that many opportunities in this decoder.
Anyhow, this is what I came up with for my 4 bit BCD to 7 segment decoder and, of course, using nothing but NOR and NOT gates:
As you can see, with a value of 0110 (6) being input in to the decoder, I am getting a 6 on the display.
Don't worry about trying to re-create this yourself (unless you want to try out my circuit above in the online logicly demo, which I don't believe can load files), I have also shared the logicly files for all three of the decoders: 2 bit decoder, 3 bit decoder, 4 bit decoder
The end result, including any optimisation that I could find myself, is that each decoder uses the following number of transistors and gates (inverters/NOT gates included):
- 2 bit decoder: 18 transistors, 14 gates
- 3 bit decoder: 58 transistors, 26 gates
- 4 bit decoder: 72 transistors, 30 gates
I think I'll leave it there for now. A similar process was followed to determine the logic for the 16 segment displays to display 3 letter month names (JAN, FEB, MAR etc) and 2 letter day of week names (MO, TU, WE etc). I'll cover this in another post.
Answer: ACD'
Hi Tom, I did the 3-bit decoder for 0..7 with 42 transistors, 19 gates, with only a tiny bit of "staring". I'll explain my system in another comment.
ReplyDeleteHowever, I just realized that only digits 0..5 are actually needed for the minutes' "tens"-counter, so that would introduce 2 "Don't-cares" per K-map. I'll try that as well and see how much more I can bring it down.
Here's the screenshot: https://github.com/meisl/discrete-nor-logic-clock/raw/master/7-seg-decoders/3bit-to-7segment-decoder(0-7)_logic.ly-screenshot.png
ReplyDeleteI also sent you a pull request, in case you want to include it.
Ah very nice. I wouldnt be surprised if my design isnt 100% optimal, and I kind of deliberately didnt go to the effort of blanking out digits 6 and 7 for the 3 bit decoder. Now Im kind of wondering if I should! :D
DeleteI will take a look and see if I can re-build them all, and do an update to this post or via another post. I havent gotten to the stage of actually building anything yet, so theres still time.
The power of the Internet. :)