Project Logs

Collapse

• Hammer = Hamming Maximiser

  Yann Guidon / YGDES • 14 hours ago • 0 comments

  So we have a unit that takes 18 bits and outputs 18 bits, whose values are as dependent from the others as permitted by only 64 XOR gates. Let's call it the H unit, because it tries to maximise the Hamming distance of the input word.
  

  This has been designed already, and I picked the encoder of a previous log:
  

  As noted before, it has some of the best possible avalanches I could find: 7 7 8 8 8 8 8 9 9 10 11 11 12 14 14 14 14 15 16 is not perfect but as good as it can be, within the constraints of parsimony of the project.
  

  We also know some of its flaws, by reading the avalanches of the reverse transform : a few combinations need only a few bits to flip only one bit, as indicated by the start of the avalanche sequence : 2 2 3 4 4...
  

  So, since the unit would be looped on itself, another permutation is required to amplify this even more, making sure these few weak bits are fed back to the strongest ones.
  

  But first, let's untangle this mess because there are a looot of crossings that would make P&R uselessly harder.

  ...........

  The untangled circuit has had a weird episode.

  The score has changed ! 7 8 8 8 8 9 9 9 9 11 12 13 14 15 15 15 15 15
  

  The 16-bit avalanche has disappeared, as well as one of the 7-bits.
  However now we have five 15 and the sum of avalanches has climbed to 200 (vs 188 for the original version, max score is 18*18=324). I don't know how or why but that's good !

  .....

  .....

  Version with even fewer crossings :
  

  I checked : same behaviours, despite changing the place of the end gates.
  

  .

  .

  .

  .

• Lemon and lemonade

  Yann Guidon / YGDES • 15 hours ago • 0 comments

  The last log has shown that the decoder has low performance. The encoder though is quite rad. I could swap them to get the desired result but that would still be insufficient. However it would be good to apply the encoder iteratively to get even better error-spreading.
  

  This means that the Hamming Maximisation circuit is not just in series with 116. NRZ FTW in the pipeline but integrated inside it. In fact the bit-flipping should be inside the feedback loop for greatest efficiency.

  And the beauty here is that the H transform (?) does not need to be a bijection, or provided in reverse form, so the unit is unique, implemented in one instance in the circuit, possibly shared by the send and receive circuits. It could increase in complexity later...

  However the study of the reverse transform informs us about some key characteristics. Those are not stellar but the iteration brings the required efficiency. It can still be increased by an output permutation, such that cyclic sequences are not too short.

  Another transformation to consider is swapping gates in the maximiser, to reduce wire crossings. I know this will be taken care of by the P&R program but there is no harm in helping it.
  

• Proof, pudding.

  Yann Guidon / YGDES • a day ago • 0 comments

  After some computations, I'm sticking to the balanced configuration with 7-14 avalanche for both decoder and encoder, and I have chosen the first one specified below:
  

  14  188 168  14  7   14  7 - 1965 7515 4021
  
  Perm1965 =
   forward(  3  5  9 17 16 10 15 12  1  2  0 14  6  7 13  8 11  4 )
   reverse( 10  8  9  0 17  1 12 13 15  2  5 16  7 14 11  6  4  3 )
  Perm7515 =
   forward( 17  2 11  0  6 16  8  9 10 14  1  7 13 15  5 12  4  3 )
   reverse(  3 10  1 17 16 14  4 11  6  7  8  2 15 12  9 13  5  0 )
  Perm4021 =
   forward(  4 17  6  5  1 15  7 14 16 13  0  9 10  8 12  2  3 11 )
   reverse( 10  4 15 16  0  3  2  6 13 11 12 17 14  9  7  5  8  1 )
  

  There are 4 variants but they are just exposing the symmetries of the tiles.

  With these sequences of number, it's now time to implement the circuit, starting from the last layer (4021)

  A first obvious feature is that the end of each cascade loops back directly to a quad inverter, so it looks good.

  CircuitJS.

  Level 2, the middle permutation layer, implements Perm7515.

  Things start to look great!

  And finally the outer permutation Perm1965. But the circuit has exceeded the size of links so I have split the decoder from the encoder.

  Encoder:

  Decoder:

  The manual checks have found that the advertised numbers don't work as expected, and look like the previous two manual version I had created before. So a 5th layer and 4th permutation would be required for a full coverage but... Let's stick to the current config for now, because that's already a lot of gates.

  • Encoder: 7 7 8 8 8 8 8 9 9 10 11 11 12 14 14 14 14 15 16 is very good !
  • Decoder: 2 2 3 4 4 5 5 6 6 6 7 7 7 7 7 8 8 9 is lousy, worse than 121. MaxHam gen2 !

  The discrepancy has no apparent reason for now. But there is a simple workaround: swap the decoder and the encoder, so avalanche is better on the receiving side.

  Another "solution" would be to loop the circuits back for another round.

  3rd solution : use the highly efficient encoder in the loop of the NRZI converter, to form a combined unit.

• Brute-forcing in C

  Yann Guidon / YGDES • 2 days ago • 0 comments

  As I try to find the best permutations in C, the tiles need to be emulated as well, and I have come up with this C code, optimised for speed on recent OOO CPUs:
  

  static inline unsigned int Encode_layer(unsigned int X) {
    // inversions
    unsigned int Y = (X & 0x02010) * 30;
  
    // Gray encoding
    unsigned int G = (X & 0x03C1E) >> 1;
  
    return X ^ Y ^ G ;
  }
  
  static inline unsigned int Decode_layer(unsigned int X) {
    unsigned int
      Y =  X & 0x02010,
      A = (Y          ) >> 4,
      B = (X & 0x03018) >> 3;
    Y = Y*30;
      A ^= (X & 0x0381C) >> 2;
      B ^= (X & 0x03C1E) >> 1;
    return X ^ Y ^ A ^ B;
  }
  

  I process both 9-bit "tiles" at once, in the same word (SWAR approach).

  For each tile, bits 5-9 are inverted by bit 4, and bits 0-4 are a Gray cascade.

  Optimising the permutation was a different story and I opted to allocate 3MB of L3 cache...
  

  ..

  ..

  ..  (typingtypingtypingtypingtypingtypingtypingtyping)
  

  ..

  And I was dubious but I got some pretty impressive results. The top ones so far look like this, after the 3rd layer :

  min    Encoder      Decoder
  sum  sum max min  sum max min  permutation #s
   5    99  15  2   165  18  3    1663:1314   
   5    99  15  2   165  18  3    1672:1476   
   5    99  15  2   165  18  3    1825:1323  
   5    99  15  2   165  18  3    1834:1485  
   5   100  12  2   118  11  3    1087:1380  
   5   100  12  2   118  11  3    1096:1542  
   5   100  12  2   118  11  3    1249:1371  
   5   100  12  2   118  11  3    1258:1533  
   5   101  14  1   145  14  4     201:1353  
   5   101  14  1   145  14  4     210:1515  
   5   101  14  1   145  14  4      39:1362  
   5   101  14  1   145  14  4      48:1524  
   5   101  14  1   159  12  4     201:1362  
   5   101  14  1   159  12  4     210:1524  
   5   101  14  1   159  12  4      39:1353  
   5   101  14  1   159  12  4      48:1515  
   5   102  11  2   120  10  3     476: 108  
   5   102  11  2   120  10  3     485: 270  
   5   102  11  2   120  10  3     638: 117  
   5   102  11  2   120  10  3     647: 279  
  

  • All of these have a sum of minimum of the avalanche = 5 : either 2 and 3 or 1 and 4
  • Both encoder and decoder have a sum of avalanches > 100, sometimes reaching 159...
  • The maximum of an individual avalanche is in the 10-14 range

  So far I have a good set of criteria to filter further brute-forcing for the 4th layer (3rd permutation). And I have optimised the heck out of it so it produces these results in under 1 second, so the further tests will take only like 20 minutes...

  And if I'm patient enough I can relax the thresholds to find more interesting and better behaving configurations.

  And it seems that 4 layers could be enough after all :-)

  .....................

  Adding the 3rd permutation, I get these results:

   Min      Encoder       Decoder
   Sum    Sum Max Min   Sum Max Min    Perm. numbers
    12    127  13  3    200  14   9    1663:1482:1458
    12    127  13  3    200  14   9    1672:1320:1467
    12    127  13  3    200  14   9    1825:1491:1296
    12    127  13  3    200  14   9    1834:1329:1305
    12    130  12  3    196  17   9     669:1154: 386
    12    130  12  3    196  17   9     678: 992: 395
    12    130  12  3    196  17   9     831:1163: 548
    12    130  12  3    196  17   9     840:1001: 557
    12     99  10  2    203  15  10     218:1241:1478
    12     99  10  2    203  15  10     227:1079:1487
    12     99  10  2    203  15  10      56:1232:1316
    12     99  10  2    203  15  10      65:1070:1325
  

  The decoder gets impressive avalanche but the encoder doesn't take off :-/ the minimum avalanche doesn't get above 3...

  Which is explained by a bug in the code ...
  

  .......................

  .......................

  And with the stupid bug found, here it goes:

   13   148 12  5   172 13  8   - 1646:1465:1157
   13   148 12  5   172 13  8   - 1655:1303:1166
   13   148 12  5   172 13  8   - 1808:1474: 995
   13   148 12  5   172 13  8   - 1817:1312:1004
   13   148 12  5   184 13  8   - 1646:1465:1166
   13   148 12  5   184 13  8   - 1655:1303:1157
   13   148 12  5   184 13  8   - 1808:1474:1004
   13   148 12  5   184 13  8   - 1817:1312: 995
   13   177 13  8   127 10  5   - 1425:1705: 762
   13   177 13  8   127 10  5   - 1434:1867: 771
   13   177 13  8   127 10  5   - 1587:1696: 924
   13   177 13  8   127 10  5   - 1596:1858: 933
   13   178 12  8   149 13  5   - 1730:  30:1314
   13   178 12  8   149 13  5   - 1739: 192:1323
   13   178 12  8   149 13  5   - 1892:  21:1476
   13   178 12  8   149 13  5   - 1901: 183:1485
   13   195 14  7   150 11  6   - 1731: 854:1016
   13   195 14  7   150 11  6   - 1740: 692:1025
   13   195 14  7   150 11  6   - 1893: 863:1178
   13   195 14  7   150 11  6   - 1902: 701:1187
   13 196 15...

  Read more »

• Brute-forcing the permutations

  Yann Guidon / YGDES • 3 days ago • 0 comments

  The manual design is getting tedious, I have to automate it.

  The final form (VHDL source code) will be something like, for the encoder :
  

  Avalanche_D
  Permutation_P1
  Avalanche_E
  Permutation_P2
  Avalanche_D
  Permutation_P3
  Avalanche_E

  For now, P1=P3 for the ease of design but it doesn't have to be so.

  The permutation can be a cyclical interleaving but the parameters must be determined and it might be too "regular".

  Then a Galois sequence is a natural choice because it is not too regular and can be reversed.

  By chance, we have 18 bits and 18+1=19 is a prime number ! so the generators are 2;3;10;13;14;15
  So for each of the 3 layers, we have 6 sequences to test, but each sequence must also be "rotated" for the 18 bits, 6*18=108 combinations. This makes 108×108×108=1,259,712 combinations to test!
  

  It is possible but not practical with GHDL. I must code it in C, along with the figures of merit. I can then use __builtin_popcount(x) and other things directly and scan the whole range in a few minutes.

  ....
  

  OK there is one more parameter to add to the generators : offset and index are different so each layer has 6×18×18=1944 combinations (should be all different). The 3 layers amount to 7,346,640,384 tests... so yeah I'll run that on 6 cores or something, and I'll strip all the computations down to the absolute minimum.

  ...

  But Galois sequences have some lousy patterns:

  Generator[0] =  2 :  1,  2,  4,  8, 16, 13,  7, 14,  9, 18, 17, 15, 11,  3,  6, 12,  5, 10
  Generator[1] =  3 :  1,  3,  9,  8,  5, 15,  7,  2,  6, 18, 16, 10, 11, 14,  4, 12, 17, 13
  Generator[2] = 10 :  1, 10,  5, 12,  6,  3, 11, 15, 17, 18,  9, 14,  7, 13, 16,  8,  4,  2
  Generator[3] = 13 :  1, 13, 17, 12,  4, 14, 11, 10, 16, 18,  6,  2,  7, 15,  5,  8,  9,  3
  Generator[4] = 14 :  1, 14,  6,  8, 17, 10,  7,  3,  4, 18,  5, 13, 11,  2,  9, 12, 16, 15
  Generator[5] = 15 :  1, 15, 16, 12,  9,  2, 11, 13,  5, 18,  4,  3,  7, 10, 17,  8,  6, 14

  The 18s are aligned, right in the middle, reminding me that the sequence is symmetrical :-/

  OTOH we have to start somewhere since 18! = 6.4E15
  

  My Galois generator can already generate 1944 sequences but that's less than 1 billionth of the sequence space, and I can't scan it exhaustively. It's possible to do 1944^2=3779136 by permuting two of these sequences. Then, it's possible to compute the pipeline up to some point, for the 18 interesting values, and be more thorough at the last stage.

  Some permutation table would help too, though I'm not sure if it would slow things down instead, because the LUT would occupy about 1MiB. Making the array would be worth it only if it is used more than a million times but it's unlikely. However, the 9-bit tiles fits in 2K bytes and it's perfect.

  ....

  C-ing...

  ...

  And I can generate 3.7 million permutations in about 0.24 second, using 3 stages of increasing buffers.
  

  #include <stdlib.h>
  #include <stdio.h>
  
  #define GENCOUNT (6)
  #define BITS     (18)
  #define MODULUS  (19)
  #define PERMS    (GENCOUNT*BITS*BITS) // 1944
  
  unsigned char generators[GENCOUNT]={ 2, 3, 10, 13, 14, 15 };
  unsigned char sequences[GENCOUNT][BITS];
  unsigned char perms[PERMS][BITS];
  
  unsigned char T[BITS];
  
  static inline void combine_perm(
      unsigned char* perm_val,
      unsigned char* perm_index,
      unsigned char* perm_dst
  ) {
    for (unsigned int i=0; i<BITS; i++)
      perm_dst[i] = perm_val[perm_index[i] & 31];
  }
  
  int main(int argc, char **argv) {
  
    for (unsigned int gen = 0; gen < GENCOUNT; gen++) {
      unsigned int generator=generators[gen];
      unsigned int num=1;
      for (unsigned int index=0; index<BITS; index++) {
        sequences[gen][index] = num;
        num = (num * generator) % MODULUS;
      }
    }
  
    unsigned int perm=0;
    // Scan 18*18*6=1944 sequences
    for (    unsigned int gen = 0;    gen < GENCOUNT; gen++) {
      for (  unsigned int index = 0;  index < BITS;   index++) {
        for (unsigned int offset = 0; offset < BITS;  offset++) {
          unsigned int i=index;
          unsigned int k=0;
          do {
            // convert Galois domain (which excludes 0) to bit index domain
            unsigned int j=sequences[gen][i]-1;
   j +=...

  Read more »

• MaxHam gen2

  Yann Guidon / YGDES • 4 days ago • 0 comments

  The previous attempt was very nice and taught me things, which I'll try to distill again, as I start coding it. Several insights affect this reboot:

  • I wanted to avalanche way too much early on
  • I should mix more at the first/outer layer
  • avoid "cancellation" by detecting "loops" of XOR that break the avalanches
  • alternate layer types so mixing is spreadier on the emitter.
  • 4 or 5 layers should be OK to reach H9 on both sides

  So we'll start with the "outer" layer:

  (please excuse the flaw at the lower-left quadrant)
  

  The Encoder layers stack becomes EDEDE, and decoder DEDED.
  

  For DE:DE, we have this sandwich:

  Avalanche for D-E: 1, 1, 1, 1, 2, 2, 2, 2, 6, 6, 6, 7, 8, 8, 9, 10, 13, 13

  Avalanche E-D : 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4, 4, 5, 5, 6, 6, 12, 12

  Now what can we do ? Copy-paste of course ! With a little permutation that will associate the low avalanches with the high ones, and vice versa.

  The Permutation P is reversed by S, which are both used 2×, and the intermediary Q is reversed by T. So overall the complexity is kept low through the duplications.
  Encoder: DPE-Q-DPE
  Decoder: DSE-T-DSE

  Once you have the 9-bit tiles, they are duplicated and linked by permutations...
  

  The result is still 64 XOR gates and a quite powerful avalanche, both forward and backward. However one of the input avalanches only to 2 bits on the transmission side...

  Sender: 2, 5, 7, 7, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 13, 13, 13, 13

  Receiver: 6, 6, 6, 6, 6, 7, 7, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12

  The sender has a bad bit with only 2 avalanches, which could be tied to the C/D bit. But that's a sub-optimal approach...

  There are two ways to go forward:

  1. add another layer. This increases latency, cost, complexity...
  2. explore the design space with an exhaustive method: let a computer generate many permutations and find the best parameters. This looks like the way to go...

• Hamming distance maximiser

  Yann Guidon / YGDES • 6 days ago • 0 comments

  A better 3-layers error propagator :

  Avalanche from a single-bit error can reach 14, and only one affects only 8. That's a success.
  

  However a whole bunch of inputs (7) still flip only 2 transmitted bits. In order to boost the avalanches there, the encoder should have a cascade too...
  

  So here is the new encoder, with its two cascades to mitigate the poor effect on the line.

  Two inputs only affect 4 bits. These can be allocated to the CD and MSB bits.

  Notice that from the data available, ALL errors with 1, 2, 3, 5, 12, 13, 14, 15, 16, 17 and 18 bits will flip at least 2 decoded bits.

  The whole pipeline is getting insane:
  

  Here is the link, I removed segments to keep the URL working.

  Total gates count for the encoder and the decoder : 64 XOR each. That's not insignificant but it's still way "cheaper" than the tens of words of FIFO that it saves, and even though the immediate error latency increases by one or two cycles, the worst cases are considerably reduced, without having to increase the avalanche in the PEAC scrambler.
  

  • Avalanche input-to-output: 4,4,6,6,6,6,6,6,7,8,8,8,8,8,9,9,10,11
  • Avalanche input-to-output: 5,5,6,7,7,8,9,9,9,9,9,9,9,9,9,10,11,11

  The worst-case error avalanche has decreased... but it's still manageable and it's a compromise for the size and the input avalanche. I'm sure there are better circuits but it's the best I can do in a day, it's a considerable improvement over the existing system.

  And now, VHDL is calling.

• A reversible mixing primitive

  Yann Guidon / YGDES • 6 days ago • 0 comments

  I think I have something interesting for the Hamming maximiser. Long story short, it's a "primitive" with 9 bits in, 9 bits out, meant to be used in layers with bit permutations between them.

  On Falstad's circuitjs: one layer.

  On the left, the encoder, on the right is the decoder, with an error injection layer.

  There are several zones of interest:

  • there's the "verbatim" bit, which has a pretty important fanout (6). It is not transformed and can be boosted in some way.
  • There are 4 "flippers", one layer deep. They could be made of slower, smaller XOR gates.
  • There is the "cascade" with gates that need more speed, and could be implemented with MAJ3 or things like that.

  Also not that the "flippers" could be merged as a XOR3 gate with the next layer.

  Conveniently the 9 bits are a divisor of 18, and it would work as well for 16 bit words (by removing one gate).

  The encoder could work well with 3 or 4 layers in the pipeline. The decoder could need a pipeline in the middle, because each primitive has a 4-XOR latency that could be too much...

  We'll have to check how many layers are required, and what amount and type of bit permutation are best.

  Here is a circuit with 3 layers, without the permutations (left unconnected so far)

  .

  A more systematic and hierarchical version is built with these combined primitives, which can communicate with neighbours.

  The error inputs are anotated with the number of affected bits at the output.

  This is meant to be combined with other identical blocks, here two are enough. In this configuration the circuit yields an avalanche between 1 and 15 bits:

  And a 3rd layer evens this all out, mostly, thanks to some 2:1 interleaving:

  As a result, all injected errors trigger an avalanche of at least 8 bits.

  Still, 8 inputs trigger only 2 changes at the encoded word, meaning that certain 2-bit errors will trigger only 1 bit of output (de-amplifying them). The below case could be handled by more interleaving but it might not be pertinent/appropriate.
  

  Anyway it's getting pretty sick ! (circuit)

  So a 4th layer (with 3:1 interleaving ?) should be "good".

  The point, now, would be to remove error de-amplification. For this, we have a good help : the encoder is the reverse of the decoder, so a single-bit input should encode to at least 4 bits.
  

  .
  

• Max Hamming

  Yann Guidon / YGDES • 12/21/2025 at 02:20 • 0 comments

  The new goal now is to utterly maximise the Hamming distance, that is: amplify the avalanche of an error.

  A typical crypto hash requires that one flipped bit at the input will avalanche to half of the output bits, and I hope to reach at least 18/2 = H9. But ideally it should be "most bits", which is theoretically difficult though (pigeonhole principle, etc.)

  The other difference with a hash is that it must be trivially reversible.

  We already have one suitable structure with the "Gray Parity" (GrayPar) circuits but this is not enough.

  Playing with the transition minimisation (TMDS) circuit (see 26. Bidir PEAC+ParPop) provides another"high avalanche" structure, which is its own inverse:
  

  However the properties are different (the mixing is controlled by only one input) and this must be mixed with the GrayPar structure for better avalanche of all the bits.
  

  I have chosen to keep the 5+5+5+3 configuration as a compromise between fanout and avalanche, at least 3 layers are then required. Ideally the "flip bit" input would be controlled by the "tip of the V" of a preceding GrayPar...
  

  So I'm working on that circuit now.

  The "trick" is to start from the end, at the decoder, maximising avalanche and then mirroring the circuits for the encoder.
  

• Checking more assumptions

  Yann Guidon / YGDES • 12/20/2025 at 09:23 • 0 comments

  I have put the CD bit in the middle of the word. It should be ok, but is it really ?

  The latest tests (32 words, 1 flipped bit) validate the heuristic.

  8 is indeed the best position, right in the middle of the word.
  
  

View all 126 project logs