Author Topic: Custom 1 wire (open drain aka I2C ) protocol bytes with CRC and ID arbitration  (Read 3236 times)

0 Members and 1 Guest are viewing this topic.

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Hello,
I'm working now on custom 1 wire protocol where bytes will be send with optional CRC (by extending data byte 8 bits by additional 2 bits).

Additionally, I'd like to have bus arbitration based on message ID, where ID is two bytes and each ID byte with optional 2 bits CRC.

It looks like that something such simple like below might work for low speed communication, where logical 0 is three times shorter than locical 1.



Each byte in message is separated by one time period (1ms @ 1kHz example below) space between bytes.
End of message can be marked as at least 3x time period release of open drain wire with pull-up to Vcc aka I2C, etc.

In many cases 1kHz signal frequency will be fine for low speed communication, but I'd like to be able detect transmision errors  at each byte - eg. receiver can put line low to indicate error eg. at the begining of the message, to tell sender there is something wrong, since it doesn't make any sense to continue while we already know probably one of the message bytes is already bad.


What kind of 2bit CRC would you suggest to do so for each byte?  ::)
 
« Last Edit: November 09, 2019, 10:00:28 pm by beduino »
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 22436
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
2 bits isn't really a CRC... or much of anything, I think?

You need 1 bit for basic parity.  You need at least 3 bits to do a sum (2^3 = 8 maximum number of bits) for example.  Hamming code needs 4 bits to correct single-bit errors for 8-bit words.  Or you get better efficiency for more, but I'm guessing that would suck.  You wouldn't want to have to decode the entire message packet (say 32 bits worth, plus check bits) just to see where it's going.

Heh, error correcting codes are probably a bad idea anyway actually, since that's the point, it needs to be detecting errors for arbitration purposes.  I mean, you can use them both ways, single-bit correcting is double-bit detecting, you can provide that as an output from the decoder.

It's kind of a weird thing anyway, regardless; you're relying on bit errors to serve a specific purpose. Which means you can't really tolerate bit errors at all.  Consider if some interference is reliably causing single bit flips that trigger the arbitration function, it'd basically be trolled by it and nothing can ever get through.

Mind, that's true of the original (I2C), not specific to your proposition.  It's all the more reason why I2C needs to be kept on board, well away from cables.

So anyway, if nothing else, I guess error checking on the ID/address alone, wouldn't really make sense.  Some check bits or CRC at the end would be good though.  And then you have good reason to use more bits, maybe a traditional CRC8, or, uh, what does I2C actually use again?..

Good luck, in any case.  Looks like your proposal is more than slow enough to bit-bang, if you're so inclined, so whatever timing, byte/word/packet length, EDC and ECC you like, are all game. :-+

As an aside, if bus-open times are symmetrical with bus-active times, I think that's basically Manchester encoding?

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 
The following users thanked this post: beduino

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
2 bits isn't really a CRC... or much of anything, I think?

You need 1 bit for basic parity.
I think I will use CRC-1 (basic parity ) two times: for first 4 bits and second time for last 4 bits, than those two CRC-1 will be attached to the end of each byte which will look like 2 bit CRC.
Another way could be compute CRC-1 of first 4 bits of byte, attach it to form 5 bit, than last 4 bits the same with attached CRC-1 will create fancy 10 bit number  >:D
Benefit by using parity check of 4 bits this way could be, we could reject message after parity check fails after 4 bits.

Some check bits or CRC at the end would be good though.  And then you have good reason to use more bits, maybe a traditional CRC8, or, uh, what does I2C actually use again?..
I've already found CRC-8 example implementaion used as additional byte at the end of I2C communication, so since I will also need to talk to different devices using I2C, probabbly it is good idea to implement CRC-8 as additional byte at the end of the more important message  :-+

 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Hamming code needs 4 bits to correct single-bit errors for 8-bit words.

I've already implemented in my AVR MPU code quite fast CRC8 function based on lookup table of 256, so now additional CRC byte is added by main loop code, than in timer ISR (10kHz) parity bits (after each 4 bits inside bytes) inserted during outputing encoded waveform and it looks like below for 3 bytes: 0x12 0x34 0x56 + 1 byte CRC8: 0xC1 :


In comparision, below the same 4 bytes send  without those 2 parity bits inserted in each byte:


NOTE: I've changed my mind and now space (1ms) between each byte in message is made by pull down, so we have easy to read even by humans transmission bits  ;)

Anyway, It could be interesting maybe support instead of those 2 additional bits per byte use additional 4bits for Hamming code to be able make this single bit correction  8)
However, when started looking for good examples howto calculate those Hammins codes for byte (8bits) I struggle to find good example to understand in detail howto implement this.
Here below on YT videos looks like quite good howto make it by hand on paper, but still too fast  ???

Calculating Hamming Codes example
       

Hamming Code - error detection and correction
       

Looks like ECC memory works on larger amouts of bytes.

Maybe, someone could help find more datailed information about those Hamming codes calculation in the case of single byte, error detection and optional correction?  :-//

 

Offline viperidae

  • Frequent Contributor
  • **
  • Posts: 306
  • Country: nz
Is there a reason you're rolling your own protocol and not using am existing one? There's 1wire and sw-can
 

Online jpanhalt

  • Super Contributor
  • ***
  • Posts: 4002
  • Country: us
Second why roll your own.   Have you looked at Maxim's 1-wire?  Also open-drain.
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Is there a reason you're rolling your own protocol and not using am existing one?
Because of, for example probably existing ones do not insert Hamming code into each send byte, to be able try correct bits or might be difficult to implement in software on small AVR MPUs like ATTiny85?
I might want also support encryption with one time pad, so it is sometimes easier chage a few lines of own code than try to understand complicated existing protocol which can be difficult to redesign to fit into what I need or modify existing library.

BTW: I've already found XOR based calculation of Hamming Code for byte (8 bit) data and created 256 bytes lookup table to place in AVR flash PROGMEM to accelerate computation of P8,P4,P2,P1 parity bits, so now it is time implement this into my custom protocol instead of those 2bit artificial CRC based on parity bits of 4 bits  :-/O



As we can see, now I do not reinvent the wheel, but thanks to a few very helpfull suggestions in this thread, I will have each byte encoded as 12bit Hamming Code by fast lookup table computation of its parity bits inserted, as well as additional CRC8 byte at the end of such custom message also lookup table in MPU flash memory 8)

I will of course take a look at SW-CAN/CAN or 1-Wire/I2C for some hints how arbitration is solved, however I've some idea howto do it in my custom protocol.
Arbitration for the moment is not a must, but nice to have feature and I belive in I can implement it in similar way CAN/I2C does or maybe other fancy way to allow important message break transmission of less important data in the middle.
That is why custom protocol maybe will be more versatile?



 

Offline rhodges

  • Frequent Contributor
  • **
  • Posts: 354
  • Country: us
  • Available for embedded projects.
    • My public libraries, code samples, and projects for STM8.
Over the years, I have played with a one-wire message system. The physical signalling was open collector at each node with one or two pull-up resistors. Voltage was nominally 10 or 12 volts, and each node has a resistor divider to get the signal in its pin's range. Each node would watch the wire while sending and back off if it detects a collision. Then it would go into receive mode and collect the rest of the message.

Each message was 128 bits long, and encoded with AES-128. If any bit is wrong, the entire message is garbage. The message could have a "magic number" of any size. Or it could rely on a large number of bits for the sender and receiver ID, while only a small number of node ID values would be valid. The AES-128 also provides message security. A sequence number in each message prevents "replay attacks" and can be another confidence field, as the sequence number should always be in a small window.
Currently developing embedded RISC-V. Recently STM32 and STM8. All are excellent choices. Past includes 6809, Z80, 8086, PIC, MIPS, PNX1302, and some 8748 and 6805. Check out my public code on github. https://github.com/unfrozen
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
The AES-128 also provides message security.
Nowadays, in the coming ages of Quantum Supremacy the only encryption technique that cannot be cracked is the one-time pad OTP   :o
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 22436
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
RSA is vulnerable to QC, AES is not (not nearly as significantly, at least). :-+

DES would be perfectly acceptable on a MCU anyway.  It's more just to show that you put in the effort to protect it against casual investigation, not to make it crypto secure.  The equivalent of putting a Masterlock(TM) lock on your garage versus an actually-good one.

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline GeorgeOfTheJungle

  • Super Contributor
  • ***
  • !
  • Posts: 2699
  • Country: tr
It's more just to show that you put in the effort to protect it against casual investigation, not to make it crypto secure.
I hope that does not become fashionable.
The further a society drifts from truth, the more it will hate those who speak it.
 

Offline jhpadjustable

  • Frequent Contributor
  • **
  • Posts: 295
  • Country: us
  • Salt 'n' pepper beard
I hope that does not become fashionable.
Too late. The cheap lock suffices to enable the severe anti-circumvention laws in many countries. Why spend time on engineering if Johnny Law will be your enforcer after the fact, at no cost to you?
"There are more things in heaven and earth, Arduino, than are dreamt of in your philosophy."
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 22436
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
It's more just to show that you put in the effort to protect it against casual investigation, not to make it crypto secure.
I hope that does not become fashionable.

:-DD :-DD :-DD

Friend, that IS all it ever was! :D  To varying degrees, of course.  But even top tier crypto is just another barrier against attack.  A finite barrier, not at all insurmountable, just impractical.

For example, even if you implement top crypto in a 8-bit MCU, well first of all you'll burn probably half your Flash on it alone, not to mention the computation time (which might drag down even a 1kbps connection like the present case).  Not to mention you'll spend more time on that, than the application code itself.  Huge footgun.  Meanwhile there's a dozen other attack vectors left open; your crypto implementation may be easily circumvented with a carefully crafted message, or race conditions, or supply voltage glitching, or decapping.  Or the com protocol is missing checks and a companion device can be used to probe the target device (common example: abusing USB device descriptor length to read out well beyond the actual descriptor table).  Or maybe you ordered the chips programmed by a 3rd party that occasionally forgot to set the lock bits, and the ROM can just be dumped with a normal programmer.

Yeah, security is not theoretical, it is practical.  No one needs perfect security, nor does anyone truly want it.  It only has to be good enough so that the effort required to circumvent it is expected to be greater than, say, circumventing a competitor's product, or for that matter just recreating the functionality from scratch.  Also, if security is bothersome to use -- it isn't security.  Example: frequently changed passwords causing users to write down their password on a post-it hanging on their monitor.

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Back to Hamming Code for 8 bit data there is something I'd like make clear - do we need extend byte with Hamming Code 4 bits included in a way:
P1 P2 D1 P4 D2 D3 D4 P8 D5 D6 D7 D8
or maybe it doesn't matter during transmision when we send byte as it is with Hamming Code bits appended
in the form easy later to find error bit for correction?  :-\
D1 D2 D3 D4 D5 D6 D7 D8  P8 P4 P2 P1

When we example byte from videos linked above we have:
Data byte: 0x4D 01001101  Hamming Code parity bits:  P8: 1  P4: 0  P2: 1  P1: 0  0x41  01000001  crc: 1010
where somekind of crc is simply: P8 P4 P2 P1 Hamming Code bits calculated from byte while sending

After receiving with D7 bit changed to 1 as in linked YT examples above we can calculate in receiver again:
Data byte: 0x4F 01001111  Hamming Code parity bits:  P8: 0  P4: 0  P2: 0  P1: 1  0x80  10000000  crc: 0001

So, according to calculation formula of Hamming Code for 8 bit data showed above we make: P8P4P2P1 XOR C8C4C2C1:
C= 1010 XOR 0001 = 1011 = 11.0 
Since C<>0 we detected the error and C=11 (decimal) shows that D7 bit changed, since when in the case of error we compose full 12 bit Hamming Code fro given byte:
P1 P2 D1 P4 D2 D3 D4 P8 D5 D6 D7 D8
it is clear which bit we need to correct to try avoid this error.

So, that is why it is not clear  for me whwther there is any requirement (advantage?) when using Hamming Code for byte to create those 12bit pattern during transmition or as I've shown above I still was able detect error and make attempt to correct D7 bit by appending those calculated Hamming Code parity bits to the end and send byte as it is untouched which makes this transmision easier to read by humans while we know last 4 bits a Hamming Codes?  ::)

What do you think?


BTW: For someone interested I've attached precomputed table of Hamming Code bits for byte to be able use lookup table intead of pure XOR calculation to speed up especially on AVR MPUs (I mean ATTiny85 for example) where there is no one step  instruction to shift bits right/left in register by given amount of bits  :o
Yes, It can be supprise for many until one looks in assembller code listing eg. for something as simply as it is  - it is not what one expects to see in assembler code for many CPUs >:D
Code: [Select]
uint8_t x= 0x1;
uint8_t y= (x<<4)

« Last Edit: November 11, 2019, 09:06:17 pm by beduino »
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 22436
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
You're just shuffling the bits around anyway.  Might as well keep them unpacked. 8)


BTW: For someone interested I've attached precomputed table of Hamming Code bits for byte to be able use lookup table intead of pure XOR calculation to speed up especially on AVR MPUs (I mean ATTiny85 for example) where there is no one step  instruction to shift bits right/left in register by given amount of bits  :o
Yes, It can be supprise for many until one looks in assembller code listing eg. for something as simply as it is  - it is not what one expects to see in assembler code for many CPUs >:D

Yeah, avr-gcc typically generates individual shifts until four or so, at which point it may generate a loop, or use the swap instruction.


Incidentally, to encourage optimal use of the swap instruction, you actually want to write:

Code: [Select]
var = (var >> 4) | (var << 4); // swap var

even if you're only using the lower nibble of the result (var & 0x0f).

Shame AVR doesn't have a parity flag, but there's #include <util/parity.h> available.

Cleverer shortcuts should be possible for the various bit patterns; the straightforward way is to simply mask the bit patterns as you go.

I would expect the software implementation for error detection would be smaller than a 256 byte lookup table, and execution time shouldn't be a problem here; the table is a lot faster to develop with though.

Tim
« Last Edit: November 11, 2019, 09:43:53 pm by T3sl4co1l »
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
I would expect the software implementation for error detection would be smaller than a 256 byte lookup table, and execution time shouldn't be a problem here; the table is a lot faster to develop with though.
256 byte lookup table is for the moment for simplicity, but 128 bytes is enougth since we need to precalculate Hamming Code 4 bits (P8 P4 P2 P1).
Instead of calculation using XOR and all this mess we get without bit shifting in one step on ATTiny85 lookup table is quite fast  8)
Code: [Select]
269                    avr_byte_crc_hamming_code:
 270                    /* prologue: function */
 271                    /* frame size = 0 */
 272                    /* stack size = 0 */
 273                    .L__stack_usage = 0
 274 0230 E82F                  mov r30,r24
 275 0232 F0E0                  ldi r31,0
 276 0234 E050                  subi r30,lo8(-(avr_byte_hamming_code_table))
 277 0236 F040                  sbci r31,hi8(-(avr_byte_hamming_code_table))
 278                    /* #APP */
 279                     ;  913 "avr_utils.c" 1
 280 0238 E491                  lpm r30, Z
I will change this Hamming Code parity bits table to support P8P4P2P1 bits in pairs, so 128 bytes in MPU flash memory.
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Yeah, avr-gcc typically generates individual shifts until four or so, at which point it may generate a loop, or use the swap instruction.
Yep, avr-gcc for ATTiny85 used for C code  something like this:
Code: [Select]
C= (C>>4) & 0xF

In assembler listing we have SWAP followed by ANDI - not so bad and quite smart ;)
Code: [Select]
...
 245 01dc 00C0      rjmp .L26
 247                .L28:
 248 01e0 8F70      andi r24,lo8(15)
 249 01e2 0895      ret
 250                .L26:
 251 01e4 8E2F      mov r24,r30
 252 01e6 8295      swap r24
 253 01e8 00C0      rjmp .L28
 

Offline beduinoTopic starter

  • Regular Contributor
  • *
  • Posts: 137
  • Country: 00
Each message was 128 bits long, and encoded with AES-128. If any bit is wrong, the entire message is garbage.
I've managed sucessfully to attach 4bits of Hamming Code to each send byte (12bits now), so if one bit will be wrong we still have a chance to correct this byte  8)


Fast byte Hamming Code calculaltion is now based on 128 byte lookup table precomputed pairs of 4 bit parity bits.

Now, imagine we apply XORed random OTP bits with each bit of send data this way- it will be very fast in comparision to AES-128 encoding assuming we have acccess to the same sources of random bits data on both sides of communication.
Of course OTP has limittaions, but sometimes it might be very usefull to encrypt something this simply way - eg. we do not need send too many data in low speed comunication.
In some cases we still could make SHA256 hash, for example with some sequence numbers and depennding on what we need it can work.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf