RFID technology has been widely used for asset tagging in a variety of industrial and government settings.
A typical application uses a serialized tag set with an encoded EPC memory and a database that links the tag’s EPC data to asset identifiers. For example, an RFID tag encoded with a 96-bit EPC code can be associated with a specific serial number computer server, machine tool, or medical device. An implicit assumption in the design of a tracking system is that the tags can be read reliably, thereby correctly identifying the asset.
However, this process can suffer from a problem called bit flipping.
bit flip
asset management labels
The vast majority of RFID tags on the market use EEPROM memory to store identification data. The charge stored in the memory cell determines the value of each bit in the identified EPC data (i.e., a charged memory cell can represent a “1”, while an empty cell can represent a “0”, and vice versa).
The state of a memory cell may become indeterminate in two potential situations. For simplicity, we assume that a charged memory cell represents a “1”.
The memory cell “leaks”, the charge deposited during encoding dissipates, causing the cell state to change, so the bit changes from “1” to “0”
The memory cell was not fully charged during encoding, and it is statistically possible for a partially charged cell to be read as a ‘0’ instead of a ‘1’†
†Technically, it is always possible for the charge bit to be interpreted as a ‘0’. However, when the specified charging threshold is exceeded, the likelihood of this happening is very small. Statistical details are well beyond the scope of this discussion.
Example scene
An example scenario might be that bin 1011 ends up changing to bin 1001 – most commonly a hex character “B” is changed to a hex “9”, which appears as a label backscattering two EPC codes. For example, using 96-bit encoding:
E280 1170 EA21 7B2A 04C2 1181 and E280 1170 EA21 792A 04C2 1181
This is rarely observed — we don’t know of any reliable data on prevalence from any chip manufacturer — but with billions of RFID tags actually deployed, the possibility cannot be ignored.
As a sanity check, consider a failure rate ε of 10-6/cell and the use of 128-bit extended EPC memory, which is available in many RFID chips, which we believe is a higher failure rate than typically observed, but the principle applies regardless What is the real exchange rate. For discussion purposes, we will ignore any time effects (ie failure time analysis). At ε = 10-6, approximately 1 in 7,812 tags are expected to exhibit a single bit flip; in addition, approximately 1 in 61.5 million tags are expected to exhibit two flipped bits, and approximately 488 billion 1 will show three flipped bits.
Reliably detect and correct unit flips
Because the failure rate is so low, single instances of bit flips can be reliably detected and corrected.
The easiest way is to encode each bit as a triple and use the “rule of majority” method to determine the correct data. In this case, a single “1” is encoded as “111” and “0” is encoded as “000”. If one bit of the triple is flipped, the other two will “vote” to cover the wrong bit. This method is very robust, as data loss requires the very, very unlikely event, the flip of two bits of any one triple. Again, considering our 128-bit encoding example above, the probability of a 2-bit flip for any one triplet, i.e. unrecoverable data loss, is:
~1/64 * (128/1,000,000) *(127/1000000) ~ 2.5 X10-10 or ~ 1 part in 3.9 billion.
This is the product of the probability that the first and second bits are flipped on a label and the probability that the second flipped bit is one of the adjacent bits in a particular triple.
In most regular scenarios, the probability of data corruption is very low. However, the tag’s data storage capacity is reduced by two-thirds, with less than 33% of the available tag memory being used for data when 128-bit memory can only hold 41 bits of information.
Detect two flipped bits
There is a less memory-intensive way to detect and correct a single flipped bit, as well as detect (but not correct) events with a much lower probability of a tag with two flipped bits.
This can be done by not encoding the tag directly, but by using a modification of a mode originally invented by Richard Hamming called SECDEC, or Single Error Correction Double Error Detection.
This mode uses additional parity bits calculated based on the payload data. As the name suggests, this algorithm allows only one flipped bit to be corrected, but allows the detection of a second flipped bit. RFID system designers must incorporate resources into the architecture to handle the less common situation of double flipping bits on a single tag.
