Use of Reed-Solomon error correction algorithm with 4-state barcodes

0
votes

I have a combined data information that requires minimum 35 bits.

Using a 4-state barcode, each bar represents 2 bits, so the above mentioned information can be translated into 18 bars.

enter image description here

I would like to add some strong error correction to this barcode, so if it's somehow damaged, it can be corrected. One of such approach is Reed-Solomon error correction.

My goal is to add as strong error correction as possible, but on the other hand I have a size limitation on the barcode. If I understood the Reed-Solomon algorithm correctly, m∙k  has to be at least the size of my message, i.e. 35 in my case.

Based on the Reed-Solomon Interactive Demo, I can go with (m, n, t, k) being (4, 15, 3, 9), which would allow me to code message up to 4∙9 = 36 bits. This would lead to code word of size 4∙15 = 60 bits, or 30 bars, but the error correction ratio t / n would be just 20.0%.

Next option is to go with (m, n, t, k) being (5, 31, 12, 7), which would allow me to code message up to 5∙7 = 35 bits. This would lead to code word of size 5∙31 = 155 bits, or 78 bars, and the error correction ratio t / n would be ~38.7%.

The first scenario requires use of barcode with 30 bars, which is nice, but 20.0% error correction is not as great as desired. The second scenario offers excellent error correction of 38.7%, but the barcode would have to have 78 bars, which is too many.

Is there some other approach or a different method, that would offer great error correction and a reasonable barcode length?

1
algorithmerror-handlingerror-correctionreed-solomongalois-field
Reed-Solomon codes are popular in part because they achieve theoretically optimal tradeoffs of error correction and length. If you want that amount of error correction, you need at least that length. - btilly

1 Answers

1
votes

You could use a shortened code word such as (5, 19, 6, 7) 31.5% correction ratio, 95 bits, 48 bars. One advantage of a shortened code word is reduced chance of mis-correction if it is allowed to correct the maximum of 6 errors. If any of the 6 error locations is outside of the range of valid locations, that is an indication of that there are more than 6 errors. The probability of mis-correction is about (19/31)^6 = 5.3%.