close-circle
Close

Going further

A project log for Numitron Hexadecimal display module

Another hexadecimal display, this one is sans transistor for the extra vintage touch, and uses only Soviet-era parts

Yann Guidon / YGDES 09/23/2017 at 18:173 Comments

The module works as expected but it's not over : I could spare at least 20 to 30 diodes.


Some diodes appear to be back-to-back and there are 27 such pairs. This could save 27 diodes. However the number pairs differing by 1 go to different rails and can't be easily merged.

So it seems I must focus on diodes in the same direction. I find 27 pairs of adjacent digits (with distance 2) where the diodes could be in common. But why limit to distance 2 ?

There could be all sorts of possible permutations. There is no obligation (apart from ease of understanding) to keep the digits in order in the layout. There IS one obligation to split the number in two halves because of the bidir ROM, which reduces the number of permutations. I wanted to analyse the permutations by hand but there are way too many.

So I must write a program and run binary convolutions...

Of course there are some places where 4 diodes could be merged into 1 and it's an additional bonus I consider, but the merge-2 is a lower-hanging fruit with higher probability and better yield.


So first, the permutations are highly reduced because numbers go in pairs. This is due to the bidir diode array, and this constrains things a lot, but also reduces the search space. Numbers can only go with +1, +2, +4 or +8).

This leaves 8 codependent pairs of numbers to permute. Permutation is easy : just shuffle the wires ! This leaves "only" 2×3×4×5×6×7=5040 permutations, multiplied by 4 because of the 4 possible polarity reversals.

But there are still a lot of redundancies because the permutation 01234567 is the same as 10325476, or 14 other permutations because numbers go in pairs. This leaves us with 5040/16=315 degenerate combinations. The redundant permutations should be avoided.

But wait ! there is more ! 01234567 is the same as 67452301 because we only care about the pairings. So it's all about pairings, and how many are there ?

1 => 0
2 => 1
3 => 3
4 => 3
5 => 3 shapes × 5 rotations
6 => 5 shapes (1, 3, 3, 2 and 6 rotations), summing to 15 again

Too lazy to check for 7 and I go to OEIS to find clues : oeis.org/search?q=1%2C3%2C3%2C15%2C15 but I don't find my sequence starting with 0. So I sketch for 7 and I get 0,1,3,3,5,5,35 (=7×5)

There is a high probability that the next number is 35 again (by construction) but at most, it is 35×8=280. Still better than 315 (and without the ×4 factor). The new number gives us A086116 with a hint in the description: "Numerator of mean deviation of a symmetrical binomial distribution on n elements." I don't see where the "Numerator of mean deviation" comes from but it sure looks like a "symmetrical binomial distribution on n elements".


Actually it's simpler than that and the only permutation that can work is the permutation of the input wires. Otherwise we'd get random numbers (and another 16×4 bits ROM for translation). This makes 2×3×4=24 permutations. Only. I suspect there could be more but the decoder would become more complex and require more relays.

There is a probability that several permutations are equally effective so their efficiencies can also be determined with the added constraint of merge-4 (two contiguous merges).

Here is how I create the recursive permutations:

function recurse(head, hl, tail) {
  var h1=hl+1;
  var tl=tail.length;
  if (tl > 1) {
    var t2=tail.slice(1);
    for (var i=0; tl > i; i++) {    
      var c=tail[i];
      head[hl]=c;
      recurse(head, h1, t2);
      t2[i]=c;
    }
  }
  else
    m+=head.join('')+tail[0]+"\n";
}
function start() {
  PreId=document.getElementById("pre");
  recurse([], 0, ['0', '1', '2', '3']);
  PreId.innerHTML=m;
}

 OK. It's not your basic schoolbook example but I had to deal with JS' idiosyncrasies and I like to do stuff "in place".

Now, because we only test merges of 2 or 4 diodes, there is no need to explore the full tree (it would result in duplicate values). The line "if (tl > 1)" thus becomes "if (tl > 2)" to halve the number of permutations. (I should have used hl instead but too late). Their order doesn't matter since we only test the permutations of the 2 lower levels.

With only 12 permutations to test, it's getting easier now...

The lower level of permutation creates an intermediary table to assemble the pairs of bidirectional lines. It's built from the standard 7 segments table :

var A=1,
    B=2,
    C=4,
    D=8,
    E=16,
    F=32,
    G=64;
var o7S=[
  A+B+C+D+E+F  ,  // 0
    B+C        ,  // 1
  A+B  +D+E  +G,  // 2
  A+B+C+D    +G,  // 3
    B+C    +F+G,  // 4
  A  +C+D  +F+G,  // 5
  A  +C+D+E+F+G,  // 6
  A+B+C        ,  // 7
  A+B+C+D+E+F+G,  // 8
  A+B+C+D  +F+G,  // 9
  A+B+C  +E+F+G,  // A
      C+D+E+F+G,  // B
  A    +D+E+F  ,  // C
    B+C+D+E  +G,  // D
  A    +D+E+F+G,  // E
  A      +E+F+G   // F
];
var A8=new Array(8); // intermediary table

Since the bidir bit can be on any of the 4 input bits, 4 tables are built by concatenating 2 output codes. The trick is to scan the table in the right order...

swap step=1 
 0 : 0000011000111111  (0, 1)
 2 : 0100111101011011  (2, 3)
 4 : 0110110101100110  (4, 5)
 6 : 0000011101111101  (...)
 8 : 0110111101111111 
10 : 0111110001110111 
12 : 0101111000111001 
14 : 0111000101111001 
 * 0123
 * 0213
 * 0312
swap step=2 
 0 : 0101101100111111 (0, 2)
 1 : 0100111100000110 (1, 3)
 4 : 0111110101100110 (4, 6)
 5 : 0000011101101101 (5, 7)
 8 : 0111011101111111 (8, A)
 9 : 0111110001101111 (9, b)
12 : 0111100100111001 (C, E)
13 : 0111000101011110 (d, F)
 * 1023
 * 1203
 * 1302
swap step=4 
 0 : 0110011000111111 
 1 : 0110110100000110 
 2 : 0111110101011011 
 3 : 0000011101001111 
 8 : 0011100101111111 
 9 : 0101111001101111 
10 : 0111100101110111 
11 : 0111000101111100 
 * 2013
 * 2103
 * 2301
swap step=8 
 0 : 0111111100111111 
 1 : 0110111100000110 
 2 : 0111011101011011 
 3 : 0111110001001111 
 4 : 0011100101100110 
 5 : 0101111001101101 
 6 : 0111100101111101 
 7 : 0111000100000111 
 * 3012
 * 3102
 * 3201

I got this table with the following code:

function shuffle(n, a, b, c) {
  return ((n&1 )<< a   )
       | ((n&2 )<<(b-1))
       | ((n&4 )<<(c-2));
}
function recurse(head, hl, tail) {
 var ...
  if (tl > 2) {
    if (hl==1) {
      j=1<<head[0];
       for (i=0; 8>i; i++){
        k= shuffle(i,tail[0], tail[1], tail[2]);
        A8[i]= o7S[k] | (o7S[k+j]<< 8); //>
        m+=k+" : "+toBin(A8[i], 16) +" \n";
      }
    }
.....

 Now that we have these tables, we can convolute !

Don't worry, it's not a naughty word. In our case it's just a AND. Here we just AND successive pairs of pairs of lines. That's it. It's some sort of sieving. The result is fewer bits set, and we count them to give a score.


Fast forward : I get the first results from convo7seg_04.html :-)

swap step=1
 * 0123    step=1   h1=0, t0=1, t1=2 pp=27
 * 0213    step=2   h1=1, t0=0, t1=2 pp=26
 * 0312    step=4   h1=2, t0=0, t1=1 pp=25
swap step=2
 * 1023    step=1   h1=0, t0=1, t1=2 pp=27
 * 1203    step=2   h1=1, t0=0, t1=2 pp=26
 * 1302    step=4   h1=2, t0=0, t1=1 pp=25
swap step=4
 * 2013    step=1   h1=0, t0=1, t1=2 pp=27
 * 2103    step=2   h1=1, t0=0, t1=2 pp=27
 * 2301    step=4   h1=2, t0=0, t1=1 pp=25
swap step=8
 * 3012    step=1   h1=0, t0=1, t1=2 pp=27
 * 3102    step=2   h1=1, t0=0, t1=2 pp=27
 * 3201    step=4   h1=2, t0=0, t1=1 pp=26

So there is some serious redundancy and quite little variation if we consider only simple pairings. 6 combination let us save 27 diodes but which is best ?


convo7seg_05.html says that 6 permutations save 33 diodes. That's 6 more, with the help of a few more traces. I've added the file to the project.

The permutation that is already wired is not optimal, with 32 saved diodes: the last stage only saves 5 diodes.

swap step=1
0000011000111111 (0, 1)
0100111101011011 (2, 3)
0110110101100110 (4, 5)
0000011101111101 (6, 7)
0110111101111111 (8, 9)
0111110001110111 (10, 11)
0101111000111001 (12, 13)
0111000101111001 (14, 15)
  * 0123    step=1   h1=0, t0=1, t1=2
0000011000011011 (0, 1)   6
0000010101100100 (2, 3)   5
0110110001110111 (4, 5)   10
0101000000111001 (6, 7)   6
pp=27
0000010000000000 (0, 1)  q=1
0100000000110001 (2, 3)  q=4
q=5  Q=32

For the next iteration, there is one case that is particularly interesting because it preserves most of the usual orders:

swap step=8
0111111100111111 (0, 8)   13
0110111100000110 (1, 9)    8
0111011101011011 (2, 10)  11
0111110001001111 (3, 11)  10
0011100101100110 (4, 12)   8
0101111001101101 (5, 13)  10
0111100101111101 (6, 14)  11
0111000100000111 (7, 15)   7
  * 3012    step=1   h1=0, t0=1, t1=2
0110111100000110 (0, 1)   8
0111010001001011 (2, 3)   8
0001100001100100 (4, 5)   5
0111000100000101 (6, 7)   6
pp=27
0110010000000010 (0, 1)  q=4
0001000000000100 (2, 3)  q=2
q=6  Q=33

It is optimal (Q=33) and all the lines are in natural order. The only change is the polarity reversal occurs on the MSB and not the LSB.

  1     111  1  (0, 8)
   D DD    D     X4
                (1, 9) (this line is empty!)
QQ  Q       Q    X2
     11  1      (2, 10)
  D    D  D  D   X4
   1       1    (3, 11)
 1    1     1   (4, 12)
   D   DD        X4
1   11    1  1  (5, 13)
  Q        Q     X2
   1   1111     (6, 14)
DD    D      D   X4
            1   (7, 15)
\_____/\_____/
  LSB    MSB 

45 diodes left now (down from 78). Add 14 for the segment steer, that's almost 60. Not bad. One line has even disappeared.

The diodes are pretty sparse and well spread out so placing/routing should be easy. However the columns must be reordered to keep a givent segment's signals close to each other.

^ ^v^v^v^v^v^v (0, 8)
^ ^   ^ ^v^v^  (1, 9)
^v^ ^v v^ ^v^v (2, 10)
^v^ ^ ^v^v v v (3, 11)
 v^v^ ^  v v^  (4, 12)
^v v^ ^v^v^  v (5, 13)
^v^v^v^v v  ^v (6, 14)
^ ^ ^    v v^v (7, 15)

The v and ^ symbols show the diodes' polarity. The condensed version becomes :

   v^v v     v (0, 8)
      ^  v^ ^     X4
^ ^     ^  v      X2
     v    ^ ^  (2, 10)
 v  ^  v     v    X4
      ^  v     (3, 11)
  ^        v^  (4, 12)
 v v  ^           X4
^      v^ ^  v (5, 13)
    ^    v        X2
 v v v^v       (6, 14)
^ ^         ^v    X4
           v   (7, 15)

This array can be used to create a new layout. There is room for compaction because, by design, there can't be more than one diode in 4 lines. The layout can be designed in two separate halves as well :-)

See you next log...

Discussions

Yann Guidon / YGDES wrote 09/24/2017 at 00:28 point

To be fair it applies to a 16×7 array with positive driving. There are more ON than OFF so I have covered a different version previously
https://hackaday.io/project/8121-discrete-yasep/log/27791-my-first-diode-matrix
https://hackaday.io/project/8121-discrete-yasep/log/26997-redneck-disintegrated-7-segments-decoder   

A "negative array" has only 34 diodes which makes the technique in this page useless.

  Are you sure? yes | no

Dr. Cockroach wrote 09/24/2017 at 00:08 point

It looks good Yann but now my head hurts trying to absorb it ;-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 09/24/2017 at 00:18 point

but the basics are simple : you can save 27 diodes if you have a suitable 4->16 decoder.

I'm now trying to make groups of 4 segments, to save a few more :-D

  Are you sure? yes | no