algorithmerror-handlingerror-correctionreed-solomongalois-field# Use of Reed-Solomon error correction algorithm with 4-state barcodes

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.

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?

Solution

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%.

- How to find and replace all occurrences of a substring in a string?
- How to find kth smallest element in a BST when the tree may be modified frequently?
- How to check whether a matrix is a framed matrix?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Identify connected subnetworks (R-igraph)
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
- Why is KNN slow with custom metric?
- Based on a condition, how to remove an item from the processed array and move it to another array?
- The simplest algorithm for poker hand evaluation
- Find longest repetitive sequence in a string
- Check if all elements in a list are identical
- Minimize sum of products of adjacent elements of an array
- Sorting an array with a repeating element (given its frequency) in linear time