Project Logs

Collapse

• Galois fields ?

  Yann Guidon / YGDES • 05/08/2025 at 00:46 • 2 comments

  If neither binary addition or a basic XOR work, then what's left ?

  I just remembered : GF2(n) with an appropriate polynomial.

  problem: it's multiplicative and 0 is a "weak value".

  ------------

  Discussing with Tim and ...

  Maybe the simplest method is

  S0 = m0 xor P0
  S1 = m1 xor P1
  S2 = P2

  This would reduce the "cancellations" down to the strictest minimum.

  But double-bit alterations are still easy : change S0 and any corresponding bit that flips P0 and bye bye.

  --------------

  Restarting from 2 bits only, here are the tables for the XOR (left) and ADD2 (right) combinations:

     | 00  01  10  11       | 00  01  10  11
  ---|---------------    ---|---------------
  00 | 00  01  10  11    00 | 00  01  10  11
  01 | 01  00  11  10    01 | 01  10  11  00
  10 | 10  11  00  01    10 | 10  11  00  01
  11 | 11  10  01  00    11 | 11  00  01  10

  They differ by only 4 bits, which is not much at all.

  There are certainly a lot of other swaps that could be added to increase the solidity of the code.

  For a column or row, there are 4! = 24 possible permutations but not all are legal because to enable recovery, the whole thing must be a bijection, and a permutation of the columns must preserve a permutation of the lines, and vice versa.

  ---------------------

  More messing around with the tables show that 24 permutations of the rows, times 24 permutations of the columns, amount to 576 valid combinations. I'll have to sieve them all to find which are the most resilient.
  

  .

  .

  .

  .

• Multi-bit errors

  Yann Guidon / YGDES • 05/06/2025 at 22:56 • 0 comments

  The recently collected stats provide a much finer picture of the behaviour of the GrayPar17+PEAC16 system.

  Keep in mind that it's a baseline and

  • C/D is not processed because PEAC16 is only 16-bit wide
  • 1-bit errors are expected to be "likely" but due to the bi-PAM3 encoding, they are also likely to affect 2 to 6 bits

  Studying the single-bit errors is useful but does not give the whole picture for real-life situations. Let's see what happens for longer bursts.

  Raw data.
  

  First remark: it handles 2, 3, 4 and 5 consecutive bits pretty well.
  

  • compared to all the others, single-bit errors are quite well managed after all.
  • length 2 holds well, better than 1, although 3× more errors go to PEAC but none are missed.
  • length 3 holds even better with only a couple of indices needing PEAC, the rest is caught 50/50 by the first 2 stages.
  • length 4 misses nothing but 4× more errors go to PEAC
  • cracks appear at length 5 with even more errors but still no miss
  • length 6 has several indices where Stage1 detects nothing and the error rate rises even more
  • length 7 is so-so

  Looking at the histograms,

  • 8 cycles reduce the error rate by about 100
  • 16 cycles does not reduce is considerably more: 2× to 10× but for 2× more time

  A quarantine of 10 or 12 cycles sounds reasonable but

  • gPEAC17 should detect faster and better.
  • the longer the quarantine, the more likely more errors will happen and prevent the system from doing any useful work.
  • If certainty is required, a NOP word or two seals the deal.

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

  • Total misses with 8 loops: 174614
  • with 16 loops: 65782

  it's really the tail's end.

• Add, Sub and errors

  Yann Guidon / YGDES • 05/06/2025 at 21:25 • 0 comments

  Looking back at the whole Add/Sub duo's mysteries.

  I reconstructed the whole circuit and realised a first thing : Add3 is not Sub3, as a Generate turns into Propagate : G(0) => P(0).

  I annotated the concerned gates:

  Turning Add3 into Sub3 is not just a copy-paste-addInverters operation.

  Another important detail: B(2) is more resilient simply because it is one XOR away (only) from the error flag. Which means there is no point in trying to make the others more resilient, though S(1) is more susceptible than S(0) which is "further away". Go figure.

  -------------------

  Adding more control inputs, I can explore the circuit deeper:

  In the case of "single errors", there is a behaviour I hadn't seen yet, since I had only looked at alterations of S0/S1/S2:

  • all changes of B (here, which corresponds to one Gray parity block) avalanche to the error flag
  • OTOH only the S2 alterations trigger an error, while S0 and S1 do not.

  (condition of test : all inputs A and B cleared...)
  

  This is good because single-bit alterations of the main data block will trigger an error, meaning it's paradoxically more "protected" than the markers. WAT.

• Not XOR, not ADD, then what ?

  Yann Guidon / YGDES • 05/06/2025 at 06:52 • 0 comments

  The stats collected in log 70. Stats with GrayPar17 and PEAC16x2 paint a strange picture...

  Initially I used XOR to combine the marker with the 3 parities and it wasn't great because they would cancel each other.

  Then ADD3 is a mixed bag: some bits are OK (S0), bad (S1) or great (S2).

  Naturally the idea is to reproduce the circuit of S2 and apply it to S0 and S1. What could go wrong this time ?

  • S0 depends on only 2 inputs and it's "meh".
  • S1 depends on 4 and it's bad, and I have no idea why.
  • S2 is "great" and depends on 6 inputs.

  So I'm going back to the ADD3 and copy-paste the circuit of S2. And to be honest I have no idea what I'm doing or how to make it work but it looks "interesting".

  Let's try...

  The table is puzzling

       000  001  010  011  100  101  110  111
  000  000  001  010  111  100  111  111  000
  001  001  010  111  100  111  110  000  001
  010  010  111  100  101  111  000  001  010
  011  111  100  101  110  000  001  010  011
  100  100  111  111  000  001  010  011  100
  101  111  110  000  001  010  011  100  101
  110  111  000  001  010  011  100  101  110
  111  000  001  010  011  100  101  110  111

  From the distance it looks like an addition table. Since it's the same boolean equation that is used and applied cyclically, there is the same total number of set bits per column (4 ones and 4 zeroes for positions 0, 1 and 2). The diagonals, and other features are typical but...

  • 111 should appear only 8 times and I see 13 occurrences on 3 diagonals.
  • there are some 110 and 101 that break a diagonal of 111.
  • The lower-right triangle looks normal for addition but the other half is weird!

  So the operation is not reversible and it can't be reused as is. But the idea is interesting !

  ------------------------------------------------------------------

  What else can be done to change the behaviour and the stats ? I haven't found any other reversible transformation and there might not be any...

  The best I can do so far is tweak the stats by adding a parity bit to the marker, like in the first iteration, which mean we're back to using a full-size ADD3. The sensitive question then is which signal is assigned to the MSB, which is normally 0.

  • To keep things simple and fast, m0×m1 would be assigned to S2 position, such that the XOR is performed during the add in the encoder.
  • But S2 is the strongest position and the XOR could also be assigned to the weakest S1 position, moving the m0×m1 earlier (fortunately in parallel with the other Gray gates).

  That means: at least 2 configurations to try and compare, derived from the earlier ADD3:

  Candidate 1:

  It's just a XOR on S2 but as mentioned before : S2 is the strongest bit so it makes no sense to mess with it.

  Candidate 2:

  A(0) xor B(0) is reported to S(1), which can be pushed/moved in a way that avoids adding more latency.
  

  Should be tested, out of curiosity.
  

  Candidate 3:

  This time, the XOR is with B(2) since S(1) only depends on A and B, so maybe making it sensitive to other signals could help.
  

  .

  And of course it doesn't work because of a stupid confusion between P(0) and G(0). The schematics above are broken.
  

  .

  More stats need also to be collected for the "plain XOR" version (instead of ADD3) as well as the other flip lengths (2, 3 and 4)
  

• Stats with GrayPar17 and PEAC16x2

  Yann Guidon / YGDES • 05/05/2025 at 22:09 • 0 comments

  I know I need a better PEAC scrambler but I first want to establish a base, with which to compare later developments.

  So I hooked the now validated GrayPar17 layer with the existing PEAC16x2 to see what would happen, and it's... interesting.

  Disclaimer:
  

  • C/D is now part of the "payload" but not processed by PEAC so some stats might be off by something or so.
    
  • Input data comes from a LFSR, which might not be representative, but injects enough "noise" to help sampling the space.

  Thing to check are
  

  • the number of iterations required to (if ever) detect an error, plot the histogram of the latency, and find an eventual upper limit (to help in defining the protocol)
  • see which lengths are harder to detect and where

  Overall GrayPar17 does a pretty good job at filtering most events, and I could refine the rough stats from 69. spurious errors.

  At first, I only check 1-bit flips. The upper limit of loop iterations is 30 though ideally it should be much shorter, but I want to see what happens.
  

  Scan of all the 20 bit positions, 100K times:
  

  ~~~ Testing PEAC16+GrayPar17 w. error ~~~
  burst length=1
  index=0   Stage1: 50019  Stage2: 49981
  index=1   Stage1:100000
  index=2   Stage1: 33246  Stage2: 66754
  index=3   Stage1: 50501  Stage2: 46343  Stage3: 3049  missed:107
  index=4   Stage1:100000
  index=5   Stage1: 33300  Stage2: 66700
  index=6   Stage1: 49853  Stage2: 43765  Stage3: 6377  missed:5
  index=7   Stage1:100000
  index=8   Stage1: 33241  Stage2: 66759
  index=9   Stage1: 50003  Stage2: 49997
  index=10  Stage1:100000
  index=11  Stage1: 33407  Stage2: 66593
  index=12  Stage1: 50307  Stage2: 46534  Stage3: 3042  missed:117
  index=13  Stage1:100000
  index=14  Stage1: 33384  Stage2: 66616
  index=15  Stage1: 49821  Stage2: 43858  Stage3: 6316  missed:5
  index=16  Stage1:100000
  index=17  Stage1: 33221  Stage2: 66779
  index=18  Stage1: 50043  Stage2: 37403  Stage3:12552  missed:2
  index=19  Stage1: 66702  Stage2: 33298

  • Stage 1 is detection out of SUB3, it should average 50% detection rate.
  • Stage 2 is immediate detection by comparison of the marker: most of the rest but could miss 1/4 (1/8)
  • Stage 3 is when the marker is not rejected immediately, but after a number of iterations.
  • Missed : PEAC has not bubbled the error to the carry in 30 cycles...

  Offending indices are 3 and 12 (1/1000th chance of missing a single bit flip), followed by 6, 15 and 18 (< 1/10000).
  

  OTOH indices 1, 4, 7, 10, 13, 16 are spot on. But that's only 1 in 3 positions.

  The other positions are caught immediately at stage 2.

  What is at indices 3 and 12 to be so sensitive ? and why is 9 not affected ?

  • 2-9-16 are the summed output of the parities and the markers, these bits do not appear fragile.
  • 3-6-12-15-18 all belong to the middle V/P2
  • in particular 3 and 12 are closely related, neighbours in the parity circuits. They share the input/output bit 6 (and 2 and 12).
  • paradoxically, the very great 1-4-7-10-13-16 signals are related to P3, which is combined by a longer chain in the ADD3/SUB3 units.
  • the remaining bits 5-8-11-14-17 are related to P1/S0 by a simple XOR.

  So the ADD3/SUB3 system might not be ideal, end-around carry could become necessary.

  .
  

  I also want to see how long it takes for an error beyond stage 2 to be detected.

  Pushing to 50 loops, I get:

   1 :   5830 - *****************************************************************************
   2 :   7574 - ****************************************************************************************************
   3 :   4492 - ************************************************************
   4 :   2897 - ***************************************
   5 :   2249 - ******************************
   6 :   1587 - *********************
   7 :   1359 - ******************
   8 :    998 - **************
   9 :    756 - **********
  10 :    599 - ********
  11 :    559 - ********
  12 :    447 - ******
  13 :    371 - *****
  14 :    317 - *****
  15 :    171 - ***
  16 :    209 - ***
  17 :    189 - ***
  18 :    155 - ***
  19 :     97 - **
  20 :    104 - **
  21 :    129 - **
  22 :     71 - *
  23 :     46 - *
  24 :     24 - *
  25 :     46 - *
  26 :     52 - *
  27 :     15 - *
  28 :     18 - *
  29 :     23 - *
  30 :     31 - *
  31 : 18...

  Read more »

• spurious errors

  Yann Guidon / YGDES • 05/05/2025 at 14:49 • 0 comments

  More testing, more bugs.

  These conditions raise the stage1 error flag when it shouldn't, though the marker result is OK anyway.
  

  $ ./peac_graypar |sort|uniq
  R:000  Q:101  S:11
  R:000  Q:110  S:10
  R:000  Q:111  S:01
  R:001  Q:110  S:11
  R:001  Q:111  S:10
  R:010  Q:111  S:11

  R= addend, Q= subtrahend, S=difference

  "WHY 6 codes ?"
  

  Common situation: R(2)='0' and Q(2)='1'.

  These codes are flagged as "forbidden" but they appear in the wild so what did I miss ?

  I have to go back to 66. ADD3-EAC ...

  The solution probably lies in the first tables

  -\+  0  1  2  3  4  5  6  7
  0    0  1  2  3  4  5  6  7
  1   -1  0  1  2  3  4  5  6
  2   -2 -1  0  1  2  3  4  5
  3   -3 -2 -1  0  1  2  3  4
  4   -4 -3 -2 -1  0  1  2  3
  5   -5 -4 -3 -2 -1  0  1  2
  6   -6 -5 -4 -3 -2 -1  0  1
  7   -7 -6 -5 -4 -3 -2 -1  0

  "The bold results are errors, 5/8th of the results can be detected as bad."

  -\+          0    1    2    3    4    5    6    7
    n   ~n
  0000 1111  0000 0001 0010 0011 0100 0101 0110 0111
  0001 1110  1111 0000 0001 0010 0011 0100 0101 0110
  0010 1101  1110 1111 0000 0001 0010 0011 0100 0101
  0011 1100  1101 1110 1111 0000 0001 0010 0011 0100
  0100 1011  1100 1101 1110 1111 0000 0001 0010 0011
  0101 1010  1011 1100 1101 1110 1111 0000 0001 0010
  0110 1001  1010 1011 1100 1101 1110 1111 0000 0001
  0111 1000  1001 1010 1011 1100 1101 1110 1111 0000

  but the 6 missing codes... They would clearly match the lower-lefft corner.

  -\+  0  1  2  3  4  5  6  7
  0    0  1  2  3  4  5  6  7
  1   -1  0  1  2  3  4  5  6
  2   -2 -1  0  1  2  3  4  5
  3   -3 -2 -1  0  1  2  3  4
  4   -4 -3 -2 -1  0  1  2  3
  5   -5 -4 -3 -2 -1  0  1  2
  6   -6 -5 -4 -3 -2 -1  0  1
  7   -7 -6 -5 -4 -3 -2 -1  0
  
  -\+          0    1    2    3    4    5    6    7
    n   ~n
  0000 1111  0000 0001 0010 0011 0100 0101 0110 0111
  0001 1110  1111 0000 0001 0010 0011 0100 0101 0110
  0010 1101  1110 1111 0000 0001 0010 0011 0100 0101
  0011 1100  1101 1110 1111 0000 0001 0010 0011 0100
  0100 1011  1100 1101 1110 1111 0000 0001 0010 0011
  0101 1010  1011 1100 1101 1110 1111 0000 0001 0010
  0110 1001  1010 1011 1100 1101 1110 1111 0000 0001
  0111 1000  1001 1010 1011 1100 1101 1110 1111 0000

  Aaand... they do.
  

  The equation for the error flag is simply S(2), and that's it !

  I must redo the circuits now.

  Do you remember the smaller circuit ?
  

  The error signal is controlled by S(2) and S(3), which is OR/NOT/OR. I can simply remove them, save 2 gates and one delay. P2 disappears from the formula.

  The new circuit is now the same gate count, latency and complexity as the adder:

  So now SUB3 is ADD3 with a few NOT here and there.
  

  And I have to fix the tests and rerun the stats.

     ~~~ Testing Add3+Sub3+errors ~~~
   attempts:224
    blocked by Sub3:128
    blocked by cmp:96
    passed anyway:0
     ~~~ Testing GrayPar17 burst ~~~
   1 : caught 45  56%  missed  0      in 80 attempts
   2 : caught 48  62%  missed  0      in 76 attempts
   3 : caught 29  40%  missed  2  3%  in 72 attempts
   4 : caught 37  54%  missed  2  3%  in 68 attempts
   5 : caught 33  54%  missed 10 16%  in 64 attempts
   6 : caught 21  35%  missed 32 53%  in 60 attempts
   7 : caught 23  41%  missed  4  7%  in 56 attempts
   8 : caught 29  22%  missed  0      in 52 attempts
   9 : caught 35  72%  missed  2  4%  in 48 attempts
  10 : caught 21  47%  missed  2  4%  in 44 attempts
  11 : caught 17  42%  missed  9 22%  in 40 attempts
  12 : caught 19  52%  missed 12 33%  in 36 attempts
  13 : caught 15  46%  missed  3  9%  in 32 attempts
  14 : caught 15  53%  missed  0      in 28 attempts
  15 : caught 15  62%  missed  1  4%  in 24 attempts
  16 : caught 11  55%  missed  2 10%  in 20 attempts
  17 : caught  9  56%  missed  5 31%  in 16 attempts
  18 : caught  5  41%  missed  1  8%  in 12 attempts
  19 : caught  6  75%  missed  0      in 8 attempts 

  It's less glorious but still good, it makes more sense and there is still this pattern that repeats every 7 bits.
  

  For comparison, 3 bits gives 12.5% miss rate in average, so most lengths (except 5, 6, 11 and 12) do a great job. The ADD3/SUB3 system however does not shine as much as before though. But these cases are move where there are so many bits that they can't be missed by PEAC.

  The whole circuit has been updated and a new archive is uploaded.

• Fewer burst errors

  Yann Guidon / YGDES • 05/04/2025 at 03:16 • 0 comments

  It seems that the work paid off !

  The last week I have redesigned many aspects of the GrayPar layer, after the lessons learned in log 57. Burst errors

  Here are the early results:

   1 : caught 44 55%  missed 12   in 80 attempts  15% :-/
   2 : caught 62 81%  missed  0   in 76 attempts    :-O
   3 : caught 68 94%  missed  0   in 72 attempts
   4 : caught 57 83%  missed  0   in 68 attempts
   5 : caught 43 67%  missed  8   in 64 attempts
   6 : caught 23 38%  missed 16   in 60 attempts  26%
   7 : caught 30 53%  missed 20   in 56 attempts  35%
   8 : caught 34 65%  missed  8   in 52 attempts  15%
   9 : caught 42 87%  missed  0   in 48 attempts
  10 : caught 31 70%  missed  8   in 44 attempts  18%
  11 : caught 29 72%  missed  4   in 40 attempts  10%
  12 : caught 25 69%  missed  0   in 36 attempts
  13 : caught 16 50%  missed 12   in 32 attempts  37%
  14 : caught 16 57%  missed  8   in 28 attempts  28%
  15 : caught 17 71%  missed  4   in 24 attempts  16%
  16 : caught 13 65%  missed  4   in 20 attempts  20%
  17 : caught 14 87%  missed  0   in 16 attempts
  18 : caught  9 75%  missed  0   in 12 attempts
  19 : caught  4 50%  missed  4   in  8 attempts  50%

  First column is the errors caught by the parity layer itself (after going through SUB3).

  Second column is comparison of the markers m0 and m1 with the difference from SUB3.

  Overall the result is impressive! 7 out of 20 lengths have not missed an error at all! Burst of 2, 3, 4 and 5 bits are immediately caught! It's better than expected!

  By comparison, the parity should catch 5/8=62.5% on the first column, and the average odd of missing is 1/8=12.5% so I guess that some stats have been pushed to other distributions.

  I'm a bit disappointed that 1-bit errors miss 3 errors in 20 cases. They are missed because each flip turns 0 into 1 at positions 2, 9 or 16: these are precisely the bits of the sum. Also they occur when the whole data word gets fully cleared: 3 rare cases when the 6 MSB are not set. It also happens 4 times for lengths 13, 14 and 15.
  

  OTOH the rate for all other burst lengths has gotten considerably better! Lengths 2, 3 and 4 are incredible! This is compatible with the alteration of one or two PAM3 symbols back-to-back.
  

  Furthermore, the patterns have shown that all the tested bursts affect the data as expected: the Gray decoder pushes the errors to the MSB so gPEAC can finish the work, in the few cases where the errors are missed.
  

  Of course, overall, only 7/8th of the errors can be caught (because there are check 3 bits, the math is the math). Another test shows that the whole codespace blindly obeys the laws of information:

  • 524288 codes out of 1048576 pass the first parity test,
  • Divide by 4 for the markers = 131072,
  • Divide by 2 for the C/D,
  • you're left with 64Ki codes, as expected.

  This new design looks more convoluted. However it is way better then the previous one: I can stick to it with more confidence now.

  .

  .

  .
  

  -----------------------------------
  

  Alright, it was too good to be true. I found the messed up copy-paste error in the test code and I must run it again. But wait...

   1 : caught 48  60%  missed  0       in 80 attempts          
   2 : caught 64  84%  missed  0       in 76 attempts          
   3 : caught 63  87%  missed  0       in 72 attempts          
   4 : caught 53  78%  missed  0       in 68 attempts          
   5 : caught 38  59%  missed  6   9%  in 64 attempts          
   6 : caught 21  35%  missed 32  53%  in 60 attempts
   7 : caught 28  50%  missed  0       in 56 attempts
   8 : caught 37  71%  missed  0       in 52 attempts
   9 : caught 43  89%  missed  0       in 48 attempts          
  10 : caught 31  70%  missed  0       in 44 attempts          
  11 : caught 22  55%  missed  6  15%  in 40 attempts          
  12 : caught 19  52%  missed 12  33%  in 36 attempts          
  13 : caught 18  56%  missed  2   6%  in 32 attempts          
  14 : caught 17  60%  missed  0       in 28 attempts          
  15 : caught 16  66%  missed  0       in 24 attempts
  16 : caught 14  70%  missed  1   5%  in 20 attempts
  17 : caught  9  56%  missed  5  31%  in 16 attempts
  18 : caught  5  41%  missed  1   8%  in 12 attempts
  19 : caught  6  75%  missed  0       in  8 attempts

  The single-bit errors have vanished and it has a clean behaviour up to 4 ! There are fewer lengths...

  Read more »

• Move the NOTs

  Yann Guidon / YGDES • 05/04/2025 at 00:32 • 0 comments

  Early test show a curious pattern:

  ghdl -a $VER GrayParity17_pak.vhdl test/test_GrayPar17.vhdl &&
   ghdl -e test_graypar17 && ./test_graypar17
     ~~~ Testing GrayPar17 ~~~
  i: 0 in: 0:0000000000000001 enc: 00000011110000000010
  i: 1 in: 0:0000000000000010 enc: 00100001110000100000
  i: 2 in: 0:0000000000000100 enc: 00000101110000001001
  i: 3 in: 0:0000000000001000 enc: 01001001110000010000
  i: 4 in: 0:0000000000010000 enc: 00000001010000100000
  i: 5 in: 0:0000000000100000 enc: 00000101110100000000
  i: 6 in: 0:0000000001000000 enc: 00000000110000001000
  i: 7 in: 0:0000000010000000 enc: 00001001110001000000
  i: 8 in: 0:0000000100000000 enc: 00000001100000010000
  i: 9 in: 0:0000001000000000 enc: 00000011110010000000
  i:10 in: 0:0000010000000000 enc: 00000001010000000100
  i:11 in: 0:0000100000000000 enc: 00000001110100000100
  i:12 in: 0:0001000000000000 enc: 00000000111000000000
  i:13 in: 0:0010000000000000 enc: 00000001111001000000
  i:14 in: 0:0100000000000000 enc: 00010001100000000000
  i:15 in: 0:1000000000000000 enc: 00010001110010000000
  i:16 in: 1:0000000000000000 enc: 10100001110000000010

  This "column" is caused by a curious set of circumstances.

  The 1s are caused by the negated XORs: I added a triplet of NOTs "just in case" so they are not strictly required (after all we have the gPEAC scrambler for this very purpose) but they could help a bit in case of uniform value (all-1s or all-0s).

  I had put them in places that looked "good", not close to each other and at the middle of the slopes of each V. One NOT per V, so that's 3 inversions, to provide odd parity. It should have appeared scattered through the word.

  And then, I added the two layers of shuffling. This totally reversed the desired effect!

  Now I should move the NOTs according to the actual index in the 20-bit word, instead of the geometry of the Gray decoders. I am not sure whether they should be kept, but they cost nothing and, before I switched to PAM3, they would have been extra-useful to recover the clock with NRZi.

  ---

  I moved the NOT to indices 3, 11 and 17 (c0, c6 and c2). This creates an odd parity on only one group.
  

  i: 0 in: 0:0000000000000001 enc: 00100010100000001010
  i: 1 in: 0:0000000000000010 enc: 00000000100000101000
  i: 2 in: 0:0000000000000100 enc: 00100100100000000001
  i: 3 in: 0:0000000000001000 enc: 01101000100000011000
  i: 4 in: 0:0000000000010000 enc: 00100000000000101000
  i: 5 in: 0:0000000000100000 enc: 00100100100100001000
  i: 6 in: 0:0000000001000000 enc: 00100001100000000000
  i: 7 in: 0:0000000010000000 enc: 00101000100001001000
  i: 8 in: 0:0000000100000000 enc: 00100000110000011000
  i: 9 in: 0:0000001000000000 enc: 00100010100010001000
  i:10 in: 0:0000010000000000 enc: 00100000000000001100
  i:11 in: 0:0000100000000000 enc: 00100000100100001100
  i:12 in: 0:0001000000000000 enc: 00100001101000001000
  i:13 in: 0:0010000000000000 enc: 00100000101001001000
  i:14 in: 0:0100000000000000 enc: 00110000110000001000
  i:15 in: 0:1000000000000000 enc: 00110000100010001000
  i:16 in: 1:0000000000000000 enc: 10000000100000001010

  It's less clustered now. But I have to update the circuit diagrams etc.

  Looks great so far.

• ADD3-EAC

  Yann Guidon / YGDES • 05/01/2025 at 00:13 • 0 comments

  The last log 65. GrayPar17 has identified one reason why the parity check failed for many unexpected cases.

  A proper interleave goes a long way but the combination with XOR exposes a flaw: XORing any pair of the 3 signals does not change the parity, so the parity error is not detected and we're left with the 1/4 odds of getting the right m0/m1 value. Is there a coding space where it's not the case? Unlikely.
  

  Standard addition might help, but it's still a bit too linear. Playing with the carry input may help, when in fact it only shifts the problem. And I'm frustrated since the last circuit couldn't catch all 1-bit and 2-bit (consecutive) errors despite 3 bits of protection.

  Checking with a table: binary addition has 1 odd in 2 to change the parity of the result and there is no clear pattern. I'm not sure there exists a coding space that behaves as I want, in the end there is only one parity bit worth of immediate detection capacity. I would need a second parity bit and we're already out of budget, since gPEAC will catch everything else.

  Binary addition could still work well, smoothing the statistics. The point here is "giving a fighting chance" to detect problems. Furthermore, the carry generated during one cycle could be reused in the next cycle, making the system a basic convolutional code.

  I have designed an 8-bit adder made of 3-input gates for the #YGREC8 project, it will help here. No idea if/how I can turn it into End-Around-Carry and whether it will make things better. At least I must try a couple versions and compare the stats.

  The resulting simplified circuit still has one cancellation spot at the MSB, hence the advantage of End-Around-Carry in this case.

  But it is still "simple enough", adding only 2 gates to the critical datapath, so let's try it.

  And it could get simpler, if we consider that one of the signals is the XNOR of m0 and m1. So in fact we only really need to add 2 bits to 3 bits, which rids us of one cancellation place if B(2) is kept 0. Which also makes us realise that we're not really adding 3 bits after all !

  The new circuit saves 2 XOR for the encoder because we simply drop the parity step, thus reducing the operand size.

  This moves the complexity to the decoder, which has to implement a subtract to recover m0 and m1. And we can detect errors if the subtraction underflows.

  -\+  0  1  2  3  4  5  6  7
  0    0  1  2  3  4  5  6  7
  1   -1  0  1  2  3  4  5  6
  2   -2 -1  0  1  2  3  4  5
  3   -3 -2 -1  0  1  2  3  4
  4   -4 -3 -2 -1  0  1  2  3
  5   -5 -4 -3 -2 -1  0  1  2
  6   -6 -5 -4 -3 -2 -1  0  1
  7   -7 -6 -5 -4 -3 -2 -1  0

  The bold results are errors, 5/8th of the results can be detected as bad.

  -\+          0    1    2    3    4    5    6    7
    n   ~n
  0000 1111  0000 0001 0010 0011 0100 0101 0110 0111
  0001 1110  1111 0000 0001 0010 0011 0100 0101 0110
  0010 1101  1110 1111 0000 0001 0010 0011 0100 0101
  0011 1100  1101 1110 1111 0000 0001 0010 0011 0100
  0100 1011  1100 1101 1110 1111 0000 0001 0010 0011
  0101 1010  1011 1100 1101 1110 1111 0000 0001 0010
  0110 1001  1010 1011 1100 1101 1110 1111 0000 0001
  0111 1000  1001 1010 1011 1100 1101 1110 1111 0000

  So if any of the 2 MSB is set, it's an error.

  Now it's a matter of transforming the classic adder and simplifying it with the constant values.
  

  Starting from the old 8-bit adder, I set C and X3 to 1 and I get this circuit:

  The critical datapath is longer but this circuit can be run in parallel with gPEAC.

  Both units are integrated in the new circuit.
  

  Now it's time to convert it to VHDL and compare with the basic XOR method.

  ------------------

  Aaaand VHDL says there's an error with the error. An error that doesn't manifests in the circuitjs sim. "Test early, test often, test everything!" but it's still promising.

  Wait, I messed with some copy-paste and found the error in the 1st layer of P&G.

  But to my surprise :
  

  Q2n := not Q2;
  X2  := R2 xor Q2n;
  P2  := R2 or  Q2n;
  G2  := R2 and Q2n;
  

   works just as well as
  

  Q2n := not Q2;
  X2  := R2 xor Q2n;
  G2  := R2 or  Q2n;
  P2  := R2 and Q2n;

  So I set G2 =...

  Read more »

• GrayPar17

  Yann Guidon / YGDES • 04/30/2025 at 21:30 • 0 comments

  The New pipeline moves the C/D signal with the data block and this changes a lot of things, but not radically and log 55. Rebuild has shown the method, so it shouldn't take long.

  There are two parameters to adjust and they are not difficult. Overall, the parity keeps a strength of 3 bits but we don't have to rely on C/D being unaffected: the gPEAC17 will take care of it all. In fact the new version makes both m0 and m1 unaffected now.

  The circuit:

  From the previous version we can remove the counters and adapt the high part.

  But C/D should be very sensitive to alterations. And the existing circuit has only 16 signals, I must create one somewhere and reallocate the permutations. From the earlier tests, it appears that a signal is more susceptible to "error cancellation" if it has more signals upstream in the cascade, which point to the "bottom of the V", next to the parity XORs, and these are also these signals that are closest to the MSB.

  OTOH, an error can't be cancelled if it hits the merge point of two Vs, where there is also a maximal avalanche. I'll choose this.

  Now, there are 16 signals and I need to add one. The Vs are "unbalanced" (in the last version) and curiously, adding one signal makes the structure symmetrical again. The new circuit shows that C/D is added at the bottom, assigned the position 16 (MSB) but a XOR is added to the top (d0).

  Being now at a merge point, C/D has fewer chances to be cancelled, unless both Vs are also cancelled, but then it requires/implies an odd parity error. And it is now one of the 3 "data" signals that are not XORed, with the longest avalanche, but even if both Vs get an error cancellation, the assignation as MSB of the output makes it privileged and most likely to affect the carry of gPEAC17.
  

  Since C/D is reassigned as MSB, there is no need to reassign all the other host-side signals. The external permutations remain. The internal permutation though needs a rewire, in particular in light of the issues identified in 57. Burst errors. The interleave must be 7 or more to ensure that all 2-bit errors are caught, by preventing "cancellation" in the same V. The interleave factor of 6 was not best, then, but we now have 17 signals, and 17 is a prime number (unlike 16) so we might get luckier this time.

  Furthermore we can add the constraint that a bit should not be neighbour of the associated m0/m1/P/ signal but it's hard to interleave since there are 3+3 groups, the only way to increase the distance enough is to put m0 and m1 at the ends of the word (b0 and b19) and P/ somewhere in the middle. Or some permutation thereof.

  So let's find a permutation for the 17-bit block, determine the signals at the edges, and finally tuck the remaining parity signal at a suitable place (if any exists), probably near b5 or b10 which are not XORed and break the symmetry a little.

  So the game starts with choosing signals from Q1, Q2 and Q3 and back to Q1. But 3 signals affect two Qs at once so they must also be located near opposite m0/m1/P, except that it would cancel said parity. So they must be close on the contrary (to cancel the cancellation) or choose something else:

  m0 <- Q1
  P/ <- Q2
  m1 <- Q3
  
  C/D <- Q1+Q3
  c5  <- Q1+Q2
  c10 <- Q2+Q3
  
  m0 <-> c10
  P/ <-> C/D
  m1 <-> c5
  

    Q1 Q2  Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 Q1 Q2 Q3 
    c0 c6 c11 
  (tbc)
  

  With the right interleave, all burst errors of 2 bits should be detected, and most 3-bit bursts as well. But the final parity decoder gets its own cancellation mechanism when 2 Qs fire simultaneously. This should not be possible :-/

  The only solution I see now is to resort to 3-bit additions instead of simple XORs. The transmitter adds, and the receiver subtracts. This adds a little bit of latency but it's for a good cause. And this time, let's make it a ones-complement version such that the carry out avalanches, instead of getting forgotten.

  ---------------------------

  Log 66. ADD3-EAC is a success so let's resume...

  Read more »

View all 74 project logs