Project Logs

Collapse

• Scrambler and descrambler: almost ready

  Yann Guidon / YGDES • an hour ago • 0 comments

  I have prototyped the scrambler and descrambler in C up to the RTL coding style, and updated the diagrams:

  I was too lazy to represent the carry bits separately.

  The source code is there. Now I just have to translate it to VHDL.
  

• Scrambler (clearer)

  Yann Guidon / YGDES • 5 days ago • 0 comments

  The new diagram is here:

  It's not changed but more precise, since the bus widths were not clear enough.

  • X contains 19 bits, as it is a concatenation of the 18 data bits (fitting the modulus) and the carry bit.
  • The adder is 18+18+1 bits, outputting 19 bits (including carry out).

  Another "trick" is that the carry bit from X does not need to be ANDed with the phase since it MUST be 0 at the end of phase 0. It can only be 1 at phase 1. (That change is not yet applied to the Y path)

  _____________________________________________________________

  Yeah, forget that, I messed up again. The ANDN must be restored...

  There is something else to consider : the carry !

  The adder is 18-bit wide, and unlike the C code, it truncates the input such that the 2nd cycle does not propagate or keep the carry out of phase 0. Actually, the carry should be "sticky" (ORed) during the phase 1.

  This is not represented here, and although putting everything in the X / Y registers simplified the overall algorithm, it confuses the schematic and RTL code. The next revision should address this.
  

• Error correction

  Yann Guidon / YGDES • 11/30/2025 at 14:50 • 0 comments

  tl;dr: it's a job for the miniPHY.
  

  __________________
  

  .
  

  Optimising bandwidth in a noisy environment is a difficult problem, that Shannon and others have fought for decades.

  There is this compromise, or dilemma, of detection versus correction : detection takes half the size of correction and since the miniMAC works as point-to-point with low latency, retransmit seems to be the simplest and lowest-effort strategy. For now the miniMAC is optimised for early detection with only 1/9th of bandwidth overhead.

  This is adapted when there is relatively low noise. miniMAC should still work with moderate noise though. So I'm shopping for a low-density error correction layer, which could go between the PHY and the MAC. Maybe this could be dynamically bypassed and/or optional, so it becomes active when the error rate exceeds a certain level, because it would eat bandwidth too.

  What bandwidth would be OK ? Another 1/8th gets us into the Hamming SECDED territory (64+8=72 bits) but it can correct only one bit per block. However, the line code might use multi-bit symbols with a mapping that maximises error diffusion, to speed up detection, so the slightest blip would alter several bits and be unrecoverable.

  Some sort of parallel Hamming code would use 8 nibbles for every 64 nibble. That's too much latency. Reed-Solomon would be worse. Hopefully a flavour of Viterbi or Treillis (TCM) could work. Not sure if Turbo-Codes, LDPC or similar could be practical.

  5-bit nibbles open the door for some trickery in GF(31), and 3-bit nibbles let us play in GF(7).

  But in the end FEC/ECC buys us some margin, maybe a 2× or 3× fewer retransmits until things really break down, at the cost of

  • Less bandwidth (The fewer retransmits are compounded by the extra bit overhead)
  • More latency (the ECC requires another buffer)
  • More circuits (more memory, more complexity)

  The other fun parts are

  • The bandwidth loss of FEC would be equivalent to reducing the transmit rate, which would also reduce the error rate (not the same ratio but still)
  • Low bandwidth loss from ECC would require longer buffers, which in turn increases latency and reduce retransmit rate

   => The gain-cost ratio of FEC is not great! A simpler and almost equivalent method would be

  • Adjusting / Slowing down the clock frequency (dynamic scaling)
  • Reducing the effective bitrate by switching the GCR table

  But errors occur and the retransmit algo might not be enough in the cases that interest us. A light touch of FEC is good to detect when things are about to get bad and still work at a decent performance. But as noted above, a "light" (low overhead) FEC requires long buffers and gets in the way of fast retransmission.

  The gPEAC18 descrambler has a detection latency of about 8 words (128 bits) and Hamming SECDED can correct 2 bit errors at most in this timeframe. That's not much and the recovered data risks being smushed and destroyed even more, in case of failure, which would do the same "error amplification" work as GrayPar. I don't know yet how much correction is possible in about 128 bits...

  Anyway https://arxiv.org/pdf/cs/0504020v2 reminds use that block codes are less efficient than convolutional codes.

  I had been trying to understand why in practice convolutional codes were generally superior
  to block codes, so I studied Andy’s paper with great interest. I realized that the path-merging
  property of convolutional codes could be depicted in what I called a trellis diagram, to contrast
  with the then-conventional tree diagram used in the analysis of sequential decoding. It was then
  only a small step to see that the Viterbi algorithm was an exact recursive algorithm for finding
  the shortest path through a trellis, and thus was actually an optimum trellis decoder. I believe
  that at that point I called Andy, and told him that he had been too modest when he asserted
  that the VA was “asymptotically optimum.”

  .

  Now, let's have another look at Wikipedia:

  • a TurboCode...

  Read more »

• Bus Inversion

  Yann Guidon / YGDES • 11/22/2025 at 03:01 • 0 comments

  In 99. Parallel bus I used the simple case of 6 bits per word and it's pretty simple.

  In 16. Run Length Limitation, reduced I used a 8-bit word and I got the circuit wrong. I just realised I needed to invert the input data before the popcount, so it could work correctly on a parallel bus and have 4 or less bits set at one time.

  The new circuit is there :

  Add the NRZ/NRZI flipflops and you got a TMPI (Transistion-Minimised Parallel Interface).

  The updated version of the 6-bit circuit is there:
  

  The source code for the 6-bit and 8-bit versions are available in parpop_20251123.tgz
  

• gPEAC18 descrambler (la suite)

  Yann Guidon / YGDES • 11/14/2025 at 04:02 • 0 comments

  The scrambler works but the last log 105. gPEAC: the circuit (2) found a problem with the descrambler: there can not be two carry inputs in the accumulation (decumulation ?) phase.

  However this is an issue IF I try to follow the mantra of "have only adders". The second phase (adjust modulo) IS actually a subtraction ! So the descrambler can use a subtracter during both phase. It's time to update the diagram and the algo. But this would work only if the subtracter is not made of an adder with inverted carry input.

  For faster execution but mostly for easier implementation (because VHDL does not permit boolean operations), a C version seems required.

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

  The port to C is doing well, at least for the scrambler.

  Tne descrambler code is in the same bloc so the registers must have different names, I have chosen A, B, C, D and T.

  Log 34. PEAC treillis helps for the init values again.

  From the scrambler side:

  • Do0 = Di0 + InitX
  • Do1 = Di1 + InitX + InitY
  • Do2 = Di2 + Do0 + InitX + InitY
            = Di2 + Di0 + 2×InitX + InitY

  From the descrambler side:

  • Di0 = Do0 - InitX
  • Di1 = Do1 - (InitX + InitY)
  • Di2 = Do2 - (Do0 + InitX + InitY) 
           = Do2 - (Di0 + 2×InitX + InitY)

  ==>

    A not initialised, B = INIT_X,  T = INIT_Y.

  Now, gPEAC18_codec.c works:

  #include <stdint.h>
  #include <inttypes.h>
  #include <stdio.h>
  
  #define MODULUS (258114)
  #define ADJUST  (262144-MODULUS)
  #define INIT_X   (56247) // "01101101110110111"
  #define INIT_Y  (111981) // "11011010101101101"
  
  int main() {
    uint64_t cycles = 0;
    int Msg = 12345,
     // scrambler
        X = INIT_X,
        Y = INIT_Y,
        X2, X3, Y2, V=0, W=0,
     // descrambler
        A, B = INIT_Y,
        B2, C=0, D=0,
        T = INIT_X;
  
    for (int j=0; j<670; j++) {
      for (int i=0; i<100000000; i++) {
  /////////////////////////////// Scrambler
        // phase0 : accumulation/Fibonacci on 19 bits + carry in
        X2 = Msg + Y + V;
        Y2 =   X + Y + W;
        X = X2;
        Y = Y2;
  
        // phase1 : modulo
        X3 = X2 + ADJUST;
        Y2 = Y  + ADJUST;
  
        V = X3 >> 18;
        W = Y2 >> 18;
  
        if (V) { X = X3 & 262143; }
        if (W) { Y = Y2 & 262143; }
  
  /////////////////////////////// Descrambling
        if (X >= MODULUS) {
          printf("\n   X OVERFLOW !!\n");
          goto the_end;
        }
  
        // phase0 : decumulation
        A = X - (C + B);
        B = T +  D + B ;
        T = X;
  
        // phase1 : modulo
        C = (A >> 18) & 1;
        if (C) { A = (A - ADJUST)& 262143; }
  
        B2 = B + ADJUST;
        D =  B2 >> 18;
        if (D) { B = B2 & 262143; }
  
        cycles++;
        if (X == INIT_X) {
          if (Y == INIT_Y) {
            goto the_end;
          }
        }
        if (A != Msg) {
          printf("\n A=%05X != Msg !\n", A);
          goto the_end;
        }
      }
      printf("%" PRId64 ": %05X  %05X\n", cycles, X, Y);
    }
  the_end:
    printf("\n%" PRId64 ": X=%05X  Y=%05X\n", cycles, X, Y);
    return 0;
  }

  The subtraction expression can be modified to an addition:
  

  A = X - (C + B);
    = X + 1+ ~(C + B);
    = X + ~B + (C^1); 
  

  so B and C are simply booleanly complemented and the carry input is simplified.
  

  Pfew.
  

  The diagram below shows the subtle changes with the handling of the carry signals:

  .

  Now the circuit must be folded back into a single pair of adders and 2 cycles, hence more MUX.

  The easiest place to start is the B pipeline which is almost a copy of the scrambler, except with an additional T register. The adder inputs are easy to allocate : one addend is B (with or without carry in), the other is MUX(T, Cst).

  The left side (message decumulating) is more peculiar. The operands of the adder are

  • (Scrambled_In, Cst) + ( /Y, A)
  • (Scrambled_In, A) + ( /Y, Cst)

  There is no advantage to either, since there is only one constant.

  And here is the result:

  Not represented : Reset and Phase signals.
  

  .
  

• gPEAC: the (other) circuit

  Yann Guidon / YGDES • 11/13/2025 at 01:32 • 0 comments

  After a few logs where the scrambler is rebuilt from the ground up,
  101. gPEAC: the circuit
  102. gPEAC circuit correction
  103. New new new modulo.
  Now is the time to address the descrambler.

  Log 6. Double parity presented PEAC_LineDescrambler.png:

  The circuit is still relevant but the naming has evolved a bit since (the names X & Y have been swapped), and C and D flags are now merged with the X & Y registers.

  It gets messy pretty fast and the treillis from 34. PEAC treillis helps me keep some sanity.
  

  .

  1)

  The first thing to do is check the validity of the input with the following circuit:

  This only catches about 1.5% of the errors but it's a quick and easy job. These errors would still be detected by gPEAC but several cycles later.

  2)

  Then there is the subtraction. And it gets a bit messier, since it adds a new 19-bit register because the result is not available immediately, let's rename it X (tied to Message_Out). X and its subtracter must go through 2 cycles:

  1. phase0 => X[18:0] := X[18] + Scrambled_In[17:0] - Y[17:0]
  2. phase1 => u[18:0] := X[18:0] + Cst
     if u[18]==1 then X[17:0] := u[17:0]

  So X has a valid output value at the next cycle, but on in ever cycle so a transparent latch or a parallel one would be required, and X[17] should be 0 (or it's an error).
  

  3)

  And now, the Y part.

  The first thing to consider is that Scrambled_In is delayed by one full cycle (two phases). So that would be register T.
  

  Then the register Y accumulates the delayed T modulo M. This is a bit like a parallel pipeline running along with the X pipeline. The 2 cycles are similar:

  1. phase0 => Y[18:0] := Y[18] + T[17:0] + Y[17:0],
     T[17:0] = Scrambled_In[17:0]
  2. phase1 => v[18:0] := Y[18:0] + Cst
     if v[18]==1 then Y[17:0] := v[17:0]

  And this time, there is no crossing or geometrical flipping, as shown in the unrolled/pipelined diagram below:

  There is another issue to solve : the carry input of the X subtractor, since -Y requires Cin to be 1, but it's already controlled by X[18]. And it's not easy to debug in plain VHDL which does not provide boolean operations.
  

  .

  .

  So the structural differences with the scrambler is that the descrambler

  - uses subtraction

  - requires an additional register T.
  

• Orbit length invariance

  Yann Guidon / YGDES • 11/12/2025 at 20:27 • 0 comments

  Testing the new modulus, I check the effect of a constant input message.

  Msg=0:

  66000000000  X=36663    Y=131746                        
  66100000000  X=159181    Y=42180                        
  66200000000  X=56730    Y=127039                        
  66300000000  X=93853    Y=158451                        
  66400000000  X=36243    Y=165031                        
  66500000000  X=71790    Y=65041                        
  66600000000  X=80476    Y=43666                        
  66623095107     done !

  Msg=1:

  66000000000  X=236773    Y=175058                        
  66100000000  X=143693    Y=108851                        
  66200000000  X=227833    Y=190930                        
  66300000000  X=246629    Y=237951                        
  66400000000  X=151749    Y=33828                        
  66500000000  X=162761    Y=46437                        
  66600000000  X=16165    Y=215837                        
  66623095107     done !
  

  Msg=2:

  66000000000  X=178770    Y=218371                        
  66100000000  X=128206    Y=175522                        
  66200000000  X=140823    Y=254822                        
  66300000000  X=141292    Y=59338                        
  66400000000  X=9141    Y=160740                        
  66500000000  X=253732    Y=27833                        
  66600000000  X=209968    Y=129893                        
  66623095107     done ! 

  Msg=3:

  66000000000  X=120766    Y=3570                        
  66100000000  X=112718    Y=242193                        
  66200000000  X=53813    Y=60600                        
  66300000000  X=35955    Y=138839                        
  66400000000  X=124647    Y=29537                        
  66500000000  X=86588    Y=9230                        
  66600000000  X=145657    Y=43950                        
  66623095107     done !

  The orbit lengths are the same, it just goes through different points.

  This proves that the "quiescent value" does not matter. I can stick to 0, any other value would be more complex to handle and wouldn't change the efficiency.
  

• New new new modulo.

  Yann Guidon / YGDES • 11/12/2025 at 07:24 • 0 comments

  This time it must be perfect.

  I had picked the wrong numbers in the full list of moduli, and I have fixed it in https://hackaday.io/project/178998-peac-pisano-with-end-around-carry-algorithm/files

  The new archive is https://cdn.hackaday.io/files/1789987658250432/gPEAC.000002-1000615.perfect.txt.gz

  So let's select numbers below 262144, with 4 to 6 MSB=1

  head -n 7236 gPEAC.000002-1000615.perfect.txt > gPEAC_perfect_262k.txt
  tail -n 1000 gPEAC_perfect_262k.txt > gPEAC_perfect_262k.1000.txt

  then add:

  obase=2

  at the start of  gPEAC_perfect_262k.1000.txt

  The other issue is that they are all even so the LSBs should be 010.

  $ cat gPEAC_perfect_262k.1000.txt |bc|grep '010$' |grep -v '101'|grep -v '1001'
  111000000000000010
  111000011111100010
  111000100010000010
  111100000001100010
  111100001000100010  <= 3 segments
  111100001110000010
  111100001111100010
  111110000111100010
  111111000000000010  <= 1 segment
  111111000001000010  <= 2 segments
  111111000111100010
  111111110001000010  <=
  

  We have a few candidates!
  

  111111000001000010 = 258114 = 3F042

  seems to be a good compromise with 2 pretty long segments:
  

  262144-258114 = 4030 = 111110111110

  Now let's verify that the orbit is 64G iterations: ((258114+1)*258114)-2 = 66623095108
  

  $ /usr/bin/time ./gpeac18_scrambler_int
  ....
  66200000000  X=56730    Y=127039                        
  66300000000  X=93853    Y=158451                        
  66400000000  X=36243    Y=165031                        
  66500000000  X=71790    Y=65041                        
  66600000000  X=80476    Y=43666                        
  66623095107     done !
  583.40user 0.01system 9:43.50elapsed 99%CPU

  The new detector is even simpler:

  Fourth time should be a charm, now.
  

  .

  Only drawback : the "worst case Fibonacci" count for an error going from MSB6 to MSB0 (6 bits, or 64×) would be 11 cycles. Counting the other segments, we get to 13. Another constant with fewer set MSB (only 3 or 4) would be a bit faster.

  It's a compromise between avalanche speed and code coverage. 111100001000100010 and 111000100010000010 would be interesting candidates as well, maybe we'll have to compare them.
  

• gPEAC circuit correction

  Yann Guidon / YGDES • 11/12/2025 at 06:09 • 0 comments

  The last log 101. gPEAC: the circuit has a little flaw...

  Test.

  Test early.

  Test often.

  Some tests have reminded the importance of the carry and the updated algorithm is

  Phase0:    accumulation
    X[18:0] := Msg[17:0] + Y[17:0] + X[18]
    Y[18:0] :=   X[17:0] + Y[17:0] + Y[18]     
  
  Phase1:    modulo
    t[18:0] := X[18:0] + Cst
    u[18:0] := Y[18:0] + Cst                
  
    X[18]:=t[18]
    if t[18]==1, X[17:0]=t[17:0]
    Y[18]:=u[18]
    if u[18]==1, Y[17:0]=u[17:0]
  

  so the carry still exists as the MSB of X and Y, which is always written and selectively used, depending on the phase.

  Thus the requirement/format for the adder is : 19 bits with carry input (still no carry out, it's the MSB).
  

  The diagram is updated:

  Fortunately, the implementation has only been in high level so far, indeed to verify the long-term behaviour. Without this carry, the cycles are very short.

  .
  

  Another big problem :

  The system loops after 32.315.302.423 iterations only !

  The modulus is maximal but not perfect !
  

• gPEAC: the circuit

  Yann Guidon / YGDES • 11/10/2025 at 08:08 • 0 comments

  Looking back at the main diagram of log 6. Double parity, there are two main big modifications to apply:

  1. Use the non-binary modulus: this is a critical requirement.
  2. Use a single adding circuit: this is a choice, a trade-off, to be examined, in the hope to reduce both silicon surface and power consumption. But it could also increase the complexity.

  .

  Let's go back to the binary version of the encoder, in PEAC_LineScrambler.png
  

  So let's start with the Two-Adder version.
  

  • The loopback of the carry is replaced by the added constant, in a second cycle. But the register remains because its value is required in the second cycle.
  • there is no prefix/parity either, it's implemented by the MSB of the adder.

  .

  For the scrambler, the algorithm becomes:

  1. Sum:
     Y1 = D:SumX = Message + X0   \_ in parallel
     X1 = C:SumY =      Y0 + X0   /
     
  2. Correction:
     IF D==1 then Y1 = SumX = Y1+ Cst
     IF C==1 then X1 = SumY = X1+ Cst.

  It's messy. And I would like to avoid adding registers or muxes, though it's blatantly required and I can't accept that yet.
  

  Anyway there is no additional register, X and Y can remain as they are, however I identify 3 MUX:

  • MX1 = X ? CST (shared by SumX and SumY)
  • MX2 = Message ? Y (SumX)
    
  • MX3 = Y ? X  (SumY)

  However SumY always depends on X at one input and it's not a problem if the Cst is applied in other places, as it reduces the number of complex Muxes.

  • SumX = ( Msg ? Y ) + ( X ? Cst ) 
  • SumY = X + ( Y ? Cst  )

  Note: due to commutativity, there are 4 combinations for SumX:

  1. ( Msg ? Y ) + ( X ? Cst )
  2. ( Msg ? Cst ) + ( X ? Y )
  3. ( X ? Y ) + ( Msg ? Cst )
  4. ( X ? Cst ) + ( Msg ? Y )

  Which reduces to the 2 first cases.
  Routing considerations would avoid crossing or meeting X and Y so I'd rather use the first case.
  

  And X and Y both have their own feedback MUX in case C or D is zero.

  And it's still confusing to have SumX go to Y and SumY go to X, which I correct in the following algo (i just swap the X and Y registers):

  • X = SumX = ( Msg ? X ) + ( Y ? Cst ) 
  • Y = SumY = Y + ( X ? Cst  )

  X and Y should be 19-bit wide, so the carry/overflow is taken into account during the 2nd stage.

  This is a general overview, with a few details left out, but

  • Message_in is: b0:b7=data, b8=C/D flag, b9-16=data, b17:b18=0
  • Scrambled_out is 18-bit wide (MSB is ignored, should be 0)
  • Only one MUX is a "complete" one with 2 data inputs (the one marked X). The others use a constant so they are implemented with AND and OR gates.
  • The X and Y registers are "normal" DFF but could also be implemented with enable-input versions, if available.
  • The "enable" signal is controlled by phase=1 and MSB of the sum=0, when no overflow occurs.
  • Scrambled_out is only available when phase=0, 2 clock cycles after Message_in is provided.
  • I have managed to prevent buss crossings : X and Y do not overlap, so
    the Y half could be mirrored/swapped to reduce wire lengths. Hence the equivalent version below:

  At this point, I'm not sure a single-adder version makes sense. there would be too much muxing and control logic...

  And it would make the tests more complex.
  

  .

  Aaaaaaaand it's already obsolete...

View all 110 project logs