RFID technology has been widely deployed for asset tagging in a variety of industrial and government settings.

The typical application uses a serialized set of tags with encoded EPC memory and a database, which links the EPC data of the tag to an asset identifier. For example, an RFID tag encoded with a 96 bit EPC code may be associated with a specific serial number computer server, machine tool or medical device. Implicit in the tracking system design is the assumption that the tag can be reliably read and, thus, the asset correctly identified.

This process, however, can be compromised with a problem known as bit-flipping.

BIT-FLIPPING

The vast majority of RFID tags in the marketplace utilize EEPROM memory to store the identification data. Charge stored in memory cells determine the value of each bit in the identifying EPC data (i.e., a charged memory cell can represent a ‘1’ while an empty cell can represent a ‘0’ or vice versa).

The state of the memory cell can become indeterminant in two potential scenarios. For simplicity, we will assume that a charged memory cell represents a ‘1’.

• The memory cell is ‘leaky’ and the charge deposited during encoding can dissipate, leading to a change in state of the cell and, thus, a bit change from ‘1’ to ‘0’
• The memory cell is incompletely charged during encoding, and, statistically, there is some probability that a partially charged cell will be read as a ‘0’ rather than ‘1’^†

^†Technically there is always a possibility that a charged bit can be interpreted as a ‘0.’ However, when the specified charge threshold is passed, the probability of this occurring is vanishingly small. The statistical details are well beyond the scope of this discussion.

Example Scenario

An example scenario might be the eventual change of bin 1011 to bin 1001 – most often observed as the change of the Hex character ‘B’ to Hex ‘9’, which manifests itself as a tag backscattering two EPC codes. For example, using 96 bit encoding:

E280 1170 EA21 7B2A 04C2 1181 and E280 1170 EA21 792A 04C2 1181

This scenario is rarely observed – and we are not aware of any reliable data on the prevalence from any chip manufacturer – but with literally billions of RFID tags deployed, the possibility cannot be ignored.

As a sanity check, consider a failure prevalence ε of 10^-6 / cell and utilization of a 128 bit extended EPC memory, which is available in many RFID chips, we believe this is a higher failure rate than is typically observed but the principle applies whatever the true rate may be. For the purposes of this discussion, we will ignore any time effects (i.e. time to failure analysis). At ε = 10^-6 one expects 1 in ~ 7,812 tags will exhibit a single bit flip; further, 1 in ~61.5 million tags can be expected to exhibit two flipped bits and 1 in ~488 billion can be expected to have three flipped bits.

RELIABLY DETECTING & CORRECTING A SINGLE BIT FLIP

With failure rates this low, it is possible to reliably detect and correct instances of a single bit flip.

The simplest method is to encode each bit as a triplet and use a ‘majority rules’ method to determine the correct data. In this scenario, a single ‘1’ is encoded as ‘111’ and ‘0’ is encoded as ‘000’. If one of the bits in the triplet flips, the other two bits will ‘vote’ to override the erring bit. This method is very robust as data loss requires the very, very unlikely event that two bits of any one triplet flip. Once again, considering our example above of a 128 bit encoding, the probability of having 2 bits of any one triplet flipped, i.e. irrecoverable data loss, is:

~1/64 * (128/1,000,000) *(127/1000000) ~ 2.5 X10^-10 or ~ 1 in 3.9 billion.

This is the product of the probabilities of a first and second bit flipping on one tag, and the probability that the second flipped bit is one of the neighboring bits in a particular triplet.

In the majority rules scenario, the probability of data corruption is very low. However, the data storage capacity of the tag is reduced by two thirds, in the case of a 128 bit memory and can hold only 41 bits of information, slightly less than 33% of the tag memory available is used for data.

DETECTING TWO FLIPPED BITS

There is a less memory-intensive method for detecting and correcting a single flipped bit, as well as detecting (but not correcting) the much lower probability event of a tag with two flipped bits.

This may be done by encoding the tag not directly but by using a modification of a schema, originally invented by Richard Hamming, known as SECDEC, or Single Error Correction Double Error Detection.

This schema uses additional parity bits calculated based on the payload data. As the name implies, the algorithm only allows for correction of one flipped bit but does allow for detection of a second flipped bit. The RFID system designer has to include recourse in the architecture to handle the much less common situation of dual flipped bits on a single tag.

Essentially, the technique calculates error correction parity bits using the bitwise representation of the data. Then, the technique calculates an additional, dual error detection parity bit over the data and the calculated parity bits. View a simple example, here.

SECDED allows for the checking of 120 bits of data with error-correction parity bits and one dual-error detection bit or ~94% of the available memory to be used, a threefold improvement on the ‘majority rules’ algorithm. Additional partitioning of the data payload further improves the scheme, allowing for the reliable correction of two flipped bits in ~96% of potential occurrences. Using ε = 10^-6 this allows for encoding of 120 bits of data with irrecoverable data loss in only a 1 in 1.54 billion tags.

CONCLUSION

In NovaTag’s implementation of SECDED, we encode the requested user data in the EPC data field. The vast majority of the time, this data is 96 bits or fewer. We process the data and encode the appropriate parity data in the user memory. Implementation of error checking can be done on the back end of the system at the user’s discretion without disrupting any previously established encoding schema.