CODEWITHSUNDEEP
autosarsafety-critical
Ankush K
Ankush K

Reputation: 55

How to Encode Boolean variable as 16 bit encoded value (Hamming Distance)

How shall a boolean variable be assigned 16-bit encoded values (e.g., Hamming code) to avoid false states due to bit flipping?

Upvotes: 1

Views: 616

Answers (2)

artless-noise-bye-due2AI
artless-noise-bye-due2AI

Reputation: 22420

How shall a boolean variable be assigned 16-bit encoded values (e.g., Hamming code) to avoid false states due to bit flipping?

TL;DR - any complement pair in the range can be used, giving 215 answers.

Consider the simple three bit example,

From Wikipedia hamming distance

Any boolean choice is any two opposite vertices. Ie, you can choice a number at random and then take it's complement. That has the maximal hamming distance. In order to detect an error of 'k' bits you need 'k+1' redundant bits. So, with 16 bits, you can detect up to 15 bit flips. In order to correct 'k' bits, you need '2k+1'. For the example, you could correct up to seven bit flips. This is a reliability versus availability choice.

So in the space 0..216-1, you have 215 possible pairs to be 'true' and 'false'.

All of this is simplistic in assuming that the errors are not correlated in any way.

Examples,

  1. What if the corruption is an address line versus a data bit?
  2. What if the probability that neighbouring bits are flipped is higher?
  3. What if the probability that neighbouring bits are zeroed?
  4. What if the probability that neighbouring bits are set high?

The fact that 'true XOR false' is all high no matter which bits you pick can allow an efficient check of any chosen 16-bit pairs. Answers to the above questions will help you pick a sub-set.

However, question 1 (can address lines flip) can say that an 8-bit is probably just as effective as a 16-bit value. If this case is possible, you should probably not do error correction. Also, the best pattern will be one that does not occur in the rest of the memory (or at least bit flips of the memory addresses).

Example detection only.

#define True  b0101010101010101
#define False b1010101010101010

/* Allocated in the middle of a zeroed memory 
 *  block to protect against low address flips? 
 */  
extern uint16_t flag;

void foo(void)
{
   if((flag ^ True) == 0)
      /* Flag is true */;
   else if((flag ^ False) == 0)
      /* Flag is false */;
   else
      /* memory corrupt */;
}

This example assumes not including 'stdbool.h' or any other conflicting definitions. There maybe better ways to declare the constants, but it should illustrate the concept.

Also, there is no protection against the code itself having a bit flip in the instructions nor a glitch in the CPU logic, which maybe on the order of probability of 2^15 flips of variable memory.

Upvotes: 1

Rishikesh Raje
Rishikesh Raje

Reputation: 8614

A boolean is defined in platform_types.h file. It is typedef as a uint8 as per the standard.

[SWS_Platform_00027] ⌈The standard AUTOSAR type boolean shall be implemented as an unsigned integer with a bit length that is the shortest one natively supported by the platform (in general 8 bits).

Also in this file TRUE and FALSE are defined as 0 and 1. This is also as per the standard [SWS_Platform_00056]

If you are willing to go outside the standard, you can change these definitions to hamming codes. But you need to be careful as

  1. TRUE and FALSE may be defined elsewhere in the project also.
  2. Some implementations may not use the macros TRUE and FALSE to assign values to boolean variables. They may use magic numbers of 0 and 1, in which case you will have errors in runtime.

Upvotes: -1

Related Questions