Project Logs

Collapse

• New new new modulo.

  Yann Guidon / YGDES • 4 hours ago • 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.
  

  .

  .

  .
  

• gPEAC circuit correction

  Yann Guidon / YGDES • 5 hours ago • 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 • 2 days ago • 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.
  

  .

  .

  .

  And now the reverse : PEAC_LineDescrambler.png

  .

• C/D in the middle

  Yann Guidon / YGDES • 2 days ago • 0 comments

  There is an excellent reason to place the "pseudoparity" bit at the gPEAC's MSB: its set/reset rate is 48% so it couldn't encode all numbers, unlike de C or D bit of the binary PEAC.

  ...
  

  However the C/D flag's position is arbitrary. And being grouped/bundled with the parity might not be the best strategy. So how about we put it in the middle ? At bit position 8 for example, it has better chances to trigger an error earlier than if it had to wait for the carry chain to avalanche to the MSB.

  It's just a matter of re-wiring a bit. It doesn't change the error detection rate but it should affect its curve's shape, a bit...
  

• Parallel bus

  Yann Guidon / YGDES • 3 days ago • 0 comments

  I have revisited 16. Run Length Limitation, reduced.
  

  This circuit has some interesting properties inside large CMOS lanes.

  It takes 6 bits, takes the popcount and if > 3 (take the MSB) then inverts the data => no more than 3 data bits are ON at the same time.

  Then a binary integrator takes these 6 bits, and at most 3 of them will be toggled in a give cycle.

  Two extra signals are required and they will toggle :

  • The Flip flag may change during every cycle
  • The clock signal transitions 2× per cycle but a "DDR" method can be used (sampling at both edges). Even better : a 4-phase clock signal, which makes it possible to sneak control signals in.

  The gPEAC's 18-bit word could be cut into 3 6-bit "nibbles" and transmitted in 3 cycles with a guaranteed number of transitions, so the energy budget can be tighter, or the margin could be increased.
  

  The Transmission Minimisation makes it suitable for CMOS since power is drawn during each transition. During every cycle, the flip bit, the clock signal and at most 3 data bits will change, instead of 6+1=7 without the circuit. There would be a better gain with a larger bus. There is also an implied parity which catches some blatant errors.

  This system would be great for CPU-RAM interchip communication too.
  

  Too bad I can't apply this to the serial link, at least directly and with tri-level signalling. TMDS works well for serial binary levels (see 33. TMDS), and also potentially for parallel 4-level signals: pairs of bits are directly encoded and the overall bus has less amplitude, so uses less power and less creates EMI.
  

• Architecture update

  Yann Guidon / YGDES • 3 days ago • 0 comments

  Version 6 of the transceiver pipeline is up on the main page:

  There is the little addition of the post-GrayPar decoder, where the result is tested with the modulus. That's a small safety net but every percentage helps in the big picture. As stated in the previous log 96. Modular adder, it prevents invalid data from entering the gPEAC registers. It can also be run in parallel so the pretty long "carry chain" does not impact the clock frequency.

  Log 34. PEAC treillis reminds that full error protection requires 2 "empty check words" so maybe the protocol should be extended by one empty word when C/D is toggled.

  The current design opts for a separate gPEAC scrambler and descrambler, to keep scheduling simple. The emitter can work independently from the receiver. A singler-adder is chosen for bandwidths below 300Mbps if we can get a fast enough adder, but 4 cycles are now required for each word.

  For a 100Mbps rate, each word is provided at 5.555MHz, so the 18-bit adder works at 22.222MHz. That's a 1/4.5 ratio instead of 1/9 but this really increases error detection.

  The scrambler+Graypar+FSM+detectors around them form the "integrity layer". I imagine it could be recycled for other purposes, such as for onchip long-range communication or even inter-processor message passing, on a chip or a PCB. Data could then be sent as 9-bit or 18-bit parallel words without going through the nibble and miniPHY layers. A further transition minimisation can then be applied, for 7-bit wide words: each 18-bit GrayPar'ed word is cut into 3 sub-words, 6 bits each, and the popcount is easy and fast to compute. Then the result is time-differentially encoded (though the 7th bit keeps its toggle rate). That will be a log for later...
  

• Coding space

  Yann Guidon / YGDES • 5 days ago • 0 comments

  The gPEAC18 scrambler uses 18 bits to represent numbers modulo 254225=0x3E111

  The 18-bit number represents different things at different points of the circuit and here is a summary of some of them.

  • At the output of the scrambler, in the internal registers, and at the input of the descrambler, 0x00000 to 0x3E110 is a valid range. 0x3E111 to 0x3FFFF means a transmission error. That's not much (3.11%) but the detection circuit from 96. Modular adder is used to sieve these rare conditions that could create problems later (if it enters the descrambler).
  • At the output of the descrambler: range 0x00000 to 0x1FFFF is valid, that's 50%. This means that it is equivalent to standard parity. However toggling the 16th bit (C/D flag) can only occur if the LSB (b0 to b15) are cleared. This effectively covers 75% of the coding space, or equivalent to 2 parity bits.
  • Thus 0x00000 and 0x10000 are the only output values that are always "valid" at any time, for a probability of 2^-17. Reaching such a state is possible but requires values that will be detected in the next cycles.

  In a previous log 91. New modulo. I had chosen 139793=0x22211 to fill almost half of the coding space (53%) and detect parity errors faster. However this greatly reduces the efficiency of the other means of error detection. We see that the new modulus reaches almost 75%, or 2 bits equivalent of detection for internally amplified errors. This effectively halves the "quarantine" period and buffer size. Errors can be detected faster and buffers are retransmitted sooner, giving almost double the performance with higher error rates.

  So the key of this design is not to detect half of the errors immediately, but to detect twice more errors. The error curve may start to peak several cycles after reception but the fall should be 2× steeper: instead of a 100× reduction in about 7 cycles (after peak), it should be 10000×. The overall design is mostly the same so 34/2=17 words are still required for quarantine but there should be almost no chance of keeping an undetected error after 20  cycles, unlike the previous version.
  

• Modular adder

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

  The time comes to put the theory into practice...

  Log 93. New new modulo. has chosen 111110000100010001 = 254225 = 0x3E111 = 5×5×10169
  which tuns into 000001111011101111 when converted for addition.

  Another way of looking at it is that this gPEAC is a PEAC18x2 with an added constant of 7919=0x1EEF, but the constant is not applied all the time!
  

  The constant can be split into 4 "segments" and the 5 MSB are a basic, simple incrementer. I know incrementers. This one is significant but still not excessive. It just means that a very small value will "hop" from LSB to b13 in 3 cycles (assuming pure Fibonacci mode) then linger for 8 cycles until reaching b16 (b17 is a bonus). 11 cycles is the worst pathological case I can create, assuming a cleared register (which is impossible), fed with a 1 word then followed with cleared words. Any attempt at "fudging" the result to make it last longer will (unlike a LFSR) accelerate the avalanche, since the MSB of the encoder is tied to 0 and there will always be a bit that can't be erased (which will then avalanche sooner or later).
  

  I use a 2-cycle circuit, first the normal addition then the constant. I have no clue how to optimise a 3-addend circuit, though I'm sure it's possible. Leave a comment if you have relevant information. But the constant is a tentative value, because the modulo requires either the operand or the result to be kept. That's why 2 cycles are required.

  • The modulo inputs are the data register, and another source that is ANDed/ORed with the constant, selected by the phase signal.
  • The modulo output is a sum and a carry. The carry goes to the MUX that selects between the addend and the sum, going back to the storage register.

  There is no incentive to create a dedicated constant-adder unit, unless the throughput was higher. In fact I could even quadruple-cycle the adder to compute both X and Y to save some gates but the MUXes and registers could become quite large. Maybe the shorter/simpler routing will help in turn.

  There is still a nagging question : which modulus is actually better ? 254225 or 139793 ? If I built a dedicated unit, it would be harder to compare them and choose from hard data.

  .

  A last concern:

  And what if the reduced value exceeds the modulus ? This is an error condition that should be flagged immediately, or else there is a risk of cancellation from later words. But the result further amplifies the error so it's even more easier to detect.

  Adding a further comparison (another subtraction) after the reduction would be too heavy, too long, for a very rare condition. But computing the difference is not required, a binary check is enough to spot a good fraction of these errors, just looking at the binary pattern:

  111110000100010001 ==> AND the 5 MSB while ORing the next cleared bits: if the OR gives 1 then there is overflow. The principle can be easily extended to the rest of the word, and the modulus has few "segments".
  

  Here is a circuit that detects a value that is equal or higher than the modulus.
  

  That's where the low number of "segments" also becomes advantageous.

  If speed requires it, the lower segments can be omitted, but this can also be delayed by one cycle anyway.

  And I have not done any NOR/NAND reduction, so the speed is still pretty good.
  

  .
  

• Meanwhile: Koopman

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

  Philip Koopman is a fantastic resource concerning everything safety, reliability, CRCs, checksums, about which he indeed wrote a book recently. And some FORTH of course. Never forget FORTH.
  

  I contacted him about PEAC in October 2022, asking for help/validation of PEAC16x2. My article was in kiosks for more than a month already (and it's now in Creative Commons so you can read it online as you like). He could not help me, as he was busy with "work on autonomous vehicle safety".
  

  Lately, looking back at his blog, I see that I missed a few things these last years, not just his book (which I'm very curious to get but I won't use Amazon).

  That's right: he has invented and released his own checksum, claiming better than HD3 (that is: detecting all error made of 1, 2 or 3 bits).

  I'll have to find the value(s) of k.
  

  No idea if he ever has somehow looked at my article but he published his own paper and the curves look nice.
  https://arxiv.org/abs/2304.13496
  http://checksumcrc.blogspot.com/2023/05/koopman-checksum.html
  http://checksumcrc.blogspot.com/2024/02/comparative-speeds-for-different.html 
  http://checksumcrc.blogspot.com/2024/03/why-to-avoid-hash-algorithms-if-what.html

  So what's the deal here?

  From my perspective it looks like some Adler where the second register is replaced by a shift.

  But WHY A SHIFT and not at least a rotation ? Part of the reason may be with the modulus which "recycles" the bits that would have been thrown away by the left shift. The k parameter alone might account for the HD1 bump compared to the "Modular Single-Sum Checksum" it is derived from. 65371 is a nice prime number with a good binary pattern.

  Apart from providing a new class of algorithms that is somewhat better (HD-wise) than the classic Fletcher, Adler and such, without a crazy increase of computation time, I am more curious than blown away.
  

  • Increasing from HD2 to HD3 is pretty nice but division is expensive. I'll have to check his implementation.
  • The use of a large, single register might be a limitation. Remember that PEAC16x2 exceeds 2G states with only 16-bit registers. And leaving the whole register exposed to incoming data increases the risk of a crash.
  • What about the "Adler defect" ? Using a modulus that is smaller than the data word creates ambiguity since two numbers could hash to the same result after the modulo. I wouldn't do that.

  Now, to address the last concern, there is something else that is interesting: a parity mode. I reinvented it these last months but it seems new to me in the literature. Quoting:
  

  ·     DualX-32P: This is DualX-32 with 15-bit modulus of 32749 and an additional parity computation. The parity computation boosts fault detection to HD=4 while still being faster than DualSum-32.

  ·     Koopman-32P: This uses a 64-bit sum variable with a modulus of 0x7FFFFFED, processing the data word one 32-bit block at a time. This is slightly slower than Koopman-32 due to an extra XOR operation with an additional parity register inside the inner loop that is used to compute parity.

  Going to HD4 is cool, at the expense of one data bit per word (or so, I'll have to double-check). Here, I'm doing (rediscovering) something similar by using the high bit (that should remain 0 even with random data) for an extra (out-of-band) data.
  .

  Now, let's not forget the different approaches and goals. Philip Koopman addresses the classic checksum case, where the data blocks are bare bytestreams that need to be preserved, in case of random access for examination. It could be in HW or SW.
  

  In this project,

  • the gPEAC acts both as a required scrambler and implicitly as a checksum, when some data words are agreed to be 0.
  • There is no need to keep the data "intact" because scrambling is actually required for line balance and EMI.
  • there is no need for a "fast software version" because it's running in HW/ASIC/FPGA only.
  • The word size can be arbitrary,...

  Read more »

• Error detection: how it fits in the protocol

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

  Important reminder: the whole system is meant to work over low-quality links with low latency, but still good enough that ECC is not required and retransmission is preferred instead, to avoid the high overhead (code/circuit size, word size, buffer size, latency, ..) of ECC. This means that buffer sizes must be kept a short as possible to reduce the latency (and BW degradation) when errors occur.

  ---

  The protocol is evolving along with the underlying "Integrity/framing" (gPEAC+GrayPar+other counters and config) which is now using the C/D bit for more things than last year.

  Note:
  

  - Multiple intertwined layers and methods contribute in their own way to safety, it's not a one-trick-solution. As noted at the end, it's a balance to find and tune.
  

  - The integrity layer is now fully decoupled from the signalling and nibble framing details. No need to change/update the word framing and error detection when the signal type changes. The word length of 18 bits is a little bit awkward but still manageable.
  

  Now, C/D bit toggles serve more purposes, both for framing and error detection. C/D detects errors in 2 main ways, since the corresponding word must be 0. Then if an error occurs:

  • Either the error has not propagated toward the MSB, a C/D transition occurs and the first word is not cleared. Error spotted.
  • Or the error propagates toward C/D and forces an early toggle, which does not correspond to the agreed-upon burst size (and the first word is not cleared either, see above).

  There is an overall decent confidence that control words, just like data/stream words, are protected, with

  • the equivalent of 2 bits of convolutional parity per word (average of 1 bit per byte, since the MSB also collects errors)
  • 16 bits (that are expected cleared) for each C/D transition to verify the PEAC state

  The C/D bit acts as a framing bit as well, so a single control word will trigger a second "clear check" cycle.

  C/D   value
   0    data
   0    data
   0    data
   1    0 (clear check)      
   1    control word
   0    0 (clear check)
   0    data
   0    data
   0    data

  Note: Since gPEAC has 36 bits of internal state, it takes about 36/2=18 words to distill them in the two MSB => We can expect an average worst case of about 20 words before a stream error is detected from the MSB, and the "clear check words" (CCW) provide 16 more check bits here and there (see below). Each CCW word adds one word of latency but it's still reasonable (and the implementation is rather simple).

  But 16 bits might not be enough to completely validate a data block (that's 1/65K chance only), so this is done in multiple complementary ways (which keeps the CCW small).
  

  • if the control word is short (such as above), then the second CCW somehow is close enough to also complete/complement the first one. The second check shadows the first one, a small latency is added but there is a validation window (it's still within 16 words).
    In other words, we can consider the whole cycle of C/D state (0-1-0) as a complete 32-bit check.

  .
  

  • Pairs of Intermediate CCWs are inserted at a configurable rate into the data stream. It's a pair of CCW that must appear at defined intervals to adjust with the BER. Each intermediate check has 2 transitions, like the above example but without the control word :
    

    C/D   value
     0    data
     0    data
     1    0 (clear check)      
     0    0 (clear check)
     0    data
     0    data

    So there is "blip" on C/D with the expected pair of 0 values that guarantee that the whole register is in the expected/right state.
    Note however that this mechanism becomes less relevant as burst sizes increase because the parity mechanism takes over for sizes > 32. So instead of [8-16-32-64-128-256-512-1024] we could just restrict this mechanism for high BER and burst sizes of [8-16-32-64] (to be determined)
    

  .
  

  • A "quarantine window" (or bufffer or FIFO) (of 16 or 32 words) guarantees that no error has percolated in the MSB anyway.

  .

  Overall, there is a compromise to find between two conflicting requirements :

  • Ensure that errors...

  Read more »

View all 103 project logs