Bugs and errors in recovering with erasures

[andrzejlisek]

I have tested the library by creating random data, corrupting the data and trying to recovery. I use the v2.1.0 release.

If I try to recovery using known error locations (erasures) thousand times, sometimes recovery fails. Below there is simple console application code, which indicates the problem:

using System;
using System.Collections.Generic;

namespace ReedSolomonTest
{
    class MainClass
    {
        /// <summary>
        /// Creating Galois field
        /// </summary>
        /// <returns>The GenericGF object</returns>
        static STH1123.ReedSolomon.GenericGF GenGF(int NumOfBits)
        {
            int PrimPoly = 0;
            switch (NumOfBits)
            {
                case 4: PrimPoly = 16 + 2 + 1; break;
                case 8: PrimPoly = 256 + 16 + 8 + 4 + 1; break;
                case 12: PrimPoly = 4096 + 64 + 16 + 2 + 1; break;
                case 16: PrimPoly = 65536 + 32 + 8 + 4 + 1; break;
                case 20: PrimPoly = 1048576 + 8 + 1; break;
                case 24: PrimPoly = 16777216 + 16 + 8 + 2 + 1; break;
                default: throw new Exception("Unsupported number of bits");
            }

            return new STH1123.ReedSolomon.GenericGF((int)PrimPoly, (int)Math.Pow(2, NumOfBits), 1);
        }


        public static void Main(string[] args)
        {
            // Number of bits per symbol
            int NumOfBits = 8;

            // Raw data block size
            int DataSize = 223;

            // Reed-Solomon code block size
            int CodeSize = 32;

            // Maximum value of element (2^n)-1, where n=1,2,3...
            int ValMax = ((int)Math.Pow(2, NumOfBits) - 1);

            // Number of randomly generated errors
            int TestErrCount = 30;

            // Determine if error locations is known
            bool KnownErrors = true;

            // Data structure with correction code
            int[] TestData1 = new int[DataSize + CodeSize];
            int[] TestData2 = new int[DataSize + CodeSize];
            int[] TestData3 = new int[DataSize + CodeSize];

            // Creating pseudo-random number generator
            Random R = new Random();

            // Maximum used value
            int MaxCodeVal = 0;

            // Good and bad result counter
            int ResultGood = 0;
            int ResultBad = 0;
            int ResultFailure = 0;

            // Number of test iterations
            int TestIterations = 1000000;

            // Iterative repeat test
            for (int TestI = 0; TestI < TestIterations; TestI++)
            {
                // Clearing data
                for (int i = 0; i < (DataSize + CodeSize); i++)
                {
                    TestData1[i] = 0;
                    TestData2[i] = 0;
                    TestData3[i] = 0;
                }

                // Creating three instances of the same raw data
                for (int i = 0; i < DataSize; i++)
                {
                    TestData1[i] = R.Next(0, ValMax);
                    TestData2[i] = TestData1[i];
                    TestData3[i] = TestData1[i];
                }

                // Encoding
                STH1123.ReedSolomon.ReedSolomonEncoder RSE = new STH1123.ReedSolomon.ReedSolomonEncoder(GenGF(NumOfBits));
                RSE.Encode(TestData2, CodeSize);


                // Making random errors with storing locations
                int TestErr = TestErrCount;
                List<int> TestErrPos = new List<int>();
                while (TestErr > 0)
                {
                    int P = R.Next(DataSize - 1);
                    if (!TestErrPos.Contains(P))
                    {
                        TestErrPos.Add(P);
                        int D = R.Next(ValMax);
                        if (TestData2[P] != D)
                        {
                            TestData2[P] = D;
                            TestData3[P] = D;
                            TestErr--;
                        }
                    }
                }

                // Trying to recovery original data
                STH1123.ReedSolomon.ReedSolomonDecoder RSD = new STH1123.ReedSolomon.ReedSolomonDecoder(GenGF(NumOfBits));
                bool DecodeResult = RSD.Decode(TestData2, CodeSize, KnownErrors ? TestErrPos.ToArray() : null);


                // Encounting differences in raw data instances
                int Diff12 = 0;
                int Diff13 = 0;
                for (int i = 0; i < DataSize; i++)
                {
                    if (TestData1[i] != TestData2[i])
                    {
                        Diff12++;
                    }
                    if (TestData1[i] != TestData3[i])
                    {
                        Diff13++;
                    }
                }

                // Reading the maximum value
                for (int i = 0; i < (DataSize + CodeSize); i++)
                {
                    if (MaxCodeVal < TestData2[i])
                    {
                        MaxCodeVal = TestData2[i];
                    }
                }

                // If there is not difference, this test result is good,
                // otherwise the test result is bad
                if (Diff13 == TestErrCount)
                {
                    if (Diff12 == 0)
                    {
                        ResultGood++;
                    }
                    else
                    {
                        ResultBad++;
                    }
                }
                else
                {
                    ResultFailure++;
                }


                // Printing the test progress
                if ((TestI % (TestIterations / 100)) == 0)
                {
                    Console.WriteLine("Progress: " + (TestI / (TestIterations / 100)) + "%");
                }
            }

            // Printing the test results
            Console.WriteLine("Maximum existing value: " + MaxCodeVal.ToString());
            Console.WriteLine("Good: " + ResultGood);
            Console.WriteLine("Bad: " + ResultBad);
            Console.WriteLine("Failed: " + ResultFailure);
            Console.WriteLine("Total: " + (ResultGood + ResultBad + ResultFailure));
            Console.ReadLine();
        }


    }
}

[Sonic-The-Hedgehog-LNK1123]

I've found a bug in your test:

bool DecodeResult = RSD.Decode(TestData2, CodeSize, KnownErrors ? TestErrPos.ToArray() : null);

The DecodeResult variable declared here is never checked in your test and introduces the bug.

Your test incorrectly assumes all the introduced errors are in fact correctable.

When I modified the test so it keeps track of the DecodeResult variable, it was "false" the same amount of times the result was "bad"

So, in those cases your test incorrectly assumes the input and output should match, while they in fact are expected to be different in those cases.

[andrzejlisek]

Let's assume, that data consists of DataSize elements and code consists of CodeSize elements.

In provided example, DataSize=223 and CodeSize=32, values are 8-bit.

I understood, that Reed-Solomon code can work in one of two ways:

1. If information about errornous values location does not exist, the Reed-Solomon code can detect and restore <=(CodeSize/2) values (less or equal to half of the number of RS code values).
2. If there is provided list of errornous (missing) values, called as erasures, the Reed-Solomon code can restore <=CodeSize values specified on the error list (less or equal to the number of RS code values).

Let's focus on the second RS code working way.

The single test is following:

1. Generate random data value array and store in two instances (both instances has identical series of values).
2. Compute the RS code for the data value serie and store it in one of the instances.
3. Randomly choose less or equal to CodeSize indexes of data part of array, store the indexes as erasure list.
4. Randomly change values at the indexes stored in erasure list.
5. Try to restore erasures using RS code.
6. Compare both instances of data serie (according your suggestion about returned DecodeResult, the false value must make such test case as bad regardless instances comparison result).

I assume, that every test case accords to fundamental restoring requirement - the number of erasures are less or equal to code elements and erasure list is provided.

Why Reed-Solomon code does not restore original values in some cases regardless meeting the fundamental requirement?

Is there some additional restoring requirement, which is not included in the test code?

[Sonic-The-Hedgehog-LNK1123]

I've now found the real bug, again, in your test:

This part:

                while (TestErr > 0)
                {
                    int P = R.Next(DataSize - 1);
                    if (!TestErrPos.Contains(P))
                    {
                        TestErrPos.Add(P);
                        int D = R.Next(ValMax);
                        if (TestData2[P] != D)
                        {
                            TestData2[P] = D;
                            TestData3[P] = D;
                            TestErr--;
                        }
                    }
                }

Should look like this:

                while (TestErr > 0)
                {
                    int P = R.Next(DataSize - 1);
                    if (!TestErrPos.Contains(P))
                    {
                        int D = R.Next(ValMax);
                        if (TestData2[P] != D)
                        {
                            TestErrPos.Add(P);
                            TestData2[P] = D;
                            TestData3[P] = D;
                            TestErr--;
                        }
                    }
                }

You are adding the position to the list too early, this causes good non-corrupted values to be flagged as bad.

In the line if (TestData2[P] != D) you are skipping to the next iteration, while the location has already been added to the erasure list, this is wrong.

With the erasure list two things are very important:

• The list may not contain duplicate values (your test is properly checking this and cause no problems at all)
• The list may not contain any indices of non-corrupted values (your test fails this requirement)

[andrzejlisek]

Before reading your answer, I found the same bug in my code and I splitted generating corruption into two explicit steps:

1. Generate list of distinct indices within data part of array.
2. Iterate over the list and change data value to another random value (the loop prevents from changing value to the same value as stored already).

Your bugfix suggestion will give the same result. The bug caused important requirement violation: The number of provided indices could exceed CodeSize value, so it caused fail such test case. I also introduced False as one of test case possible results, which occurs when Decode returns false value.

The whole test code are following, I ran the code once, it took long time and all test cases passed.

using System;
using System.Collections.Generic;

namespace ReedSolomonTest
{
    class MainClass
    {
        /// <summary>
        /// Creating Galois field
        /// </summary>
        /// <returns>The GenericGF object</returns>
        static STH1123.ReedSolomon.GenericGF GenGF(int NumOfBits)
        {
            int PrimPoly = 0;
            switch (NumOfBits)
            {
                case 2: PrimPoly = 4 + 2 + 1; break;
                case 3: PrimPoly = 8 + 2 + 1; break;
                case 4: PrimPoly = 16 + 2 + 1; break;
                case 5: PrimPoly = 32 + 4 + 1; break;
                case 6: PrimPoly = 64 + 2 + 1; break;
                case 7: PrimPoly = 128 + 2 + 1; break;
                case 8: PrimPoly = 256 + 16 + 8 + 4 + 1; break;
                case 9: PrimPoly = 512 + 16 + 1; break;
                case 10: PrimPoly = 1024 + 8 + 1; break;
                case 11: PrimPoly = 2048 + 4 + 1; break;
                case 12: PrimPoly = 4096 + 64 + 16 + 2 + 1; break;
                case 13: PrimPoly = 8192 + 16 + 8 + 2 + 1; break;
                case 14: PrimPoly = 16384 + 32 + 8 + 2 + 1; break;
                case 15: PrimPoly = 32768 + 2 + 1; break;
                case 16: PrimPoly = 65536 + 32 + 8 + 4 + 1; break;
                case 17: PrimPoly = 131072 + 8 + 1; break;
                case 18: PrimPoly = 262144 + 32 + 4 + 2 + 1; break;
                case 19: PrimPoly = 524288 + 32 + 4 + 2 + 1; break;
                case 20: PrimPoly = 1048576 + 8 + 1; break;
                case 21: PrimPoly = 2097152 + 4 + 1; break;
                case 22: PrimPoly = 4194304 + 2 + 1; break;
                case 23: PrimPoly = 8388608 + 32 + 1; break;
                case 24: PrimPoly = 16777216 + 16 + 8 + 2 + 1; break;
                case 25: PrimPoly = 33554432 + 8 + 1; break;
                case 26: PrimPoly = 67108864 + 64 + 4 + 2 + 1; break;
                case 27: PrimPoly = 134217728 + 32 + 4 + 2 + 1; break;
                case 28: PrimPoly = 268435456 + 8 + 1; break;
                case 29: PrimPoly = 536870912 + 4 + 1; break;
                case 30: PrimPoly = 1073741824 + 64 + 16 + 2 + 1; break;
                default: throw new Exception("Unsupported number of bits");
            }

            return new STH1123.ReedSolomon.GenericGF(PrimPoly, (int)Math.Pow(2, NumOfBits), 1);
        }


        public static void Main(string[] args)
        {
            // Number of bits per symbol
            int NumOfBits = 8;

            // Raw data block size
            int DataSize = 223;

            // Reed-Solomon code block size
            int CodeSize = 32;

            // Maximum value of element (2^n)-1, where n=1,2,3...
            int ValMax = ((int)Math.Pow(2, NumOfBits) - 1);

            // Number of randomly generated errors
            int TestErrCount = 31;

            // Determine if error locations is known
            bool KnownErrors = true;

            // Data structure with correction code
            int[] TestData1 = new int[DataSize + CodeSize];
            int[] TestData2 = new int[DataSize + CodeSize];
            int[] TestData3 = new int[DataSize + CodeSize];

            // Creating pseudo-random number generator
            Random R = new Random();

            // Maximum used value
            long MaxCodeVal = 0;

            // Good and bad result counter
            int ResultGood = 0;
            int ResultBad = 0;
            int ResultFalse = 0;
            int ResultFailure = 0;

            // Number of test iterations
            int TestIterations = 1000000;

            // Iterative repeat test
            for (int TestI = 0; TestI < TestIterations; TestI++)
            {
                // Clearing data
                for (int i = 0; i < (DataSize + CodeSize); i++)
                {
                    TestData1[i] = 0;
                    TestData2[i] = 0;
                    TestData3[i] = 0;
                }

                // Creating three instances of the same raw data
                for (int i = 0; i < DataSize; i++)
                {
                    TestData1[i] = R.Next(0, ValMax);
                    TestData2[i] = TestData1[i];
                    TestData3[i] = TestData1[i];
                }

                // Encoding
                STH1123.ReedSolomon.ReedSolomonEncoder RSE = new STH1123.ReedSolomon.ReedSolomonEncoder(GenGF(NumOfBits));
                RSE.Encode(TestData2, CodeSize);


                // Making erasure/error list of indices
                int TestErr = TestErrCount;
                List<int> TestErrPos = new List<int>();
                while (TestErr > 0)
                {
                    int P = R.Next(DataSize - 1);
                    if (!TestErrPos.Contains(P))
                    {
                        TestErrPos.Add(P);
                        TestErr--;
                    }
                }

                // Change value of errornous elements
                foreach (int item in TestErrPos)
                {
                    int V = TestData2[item];
                    while (TestData2[item] == V)
                    {
                        V = R.Next(ValMax);
                    }
                    TestData2[item] = V;
                    TestData3[item] = V;
                }


                // Trying to recovery original data
                STH1123.ReedSolomon.ReedSolomonDecoder RSD = new STH1123.ReedSolomon.ReedSolomonDecoder(GenGF(NumOfBits));
                bool DecodeResult = RSD.Decode(TestData2, CodeSize, KnownErrors ? TestErrPos.ToArray() : null);

                if (DecodeResult)
                {

                    // Encounting differences in raw data instances
                    int Diff12 = 0;
                    int Diff13 = 0;
                    for (int i = 0; i < DataSize; i++)
                    {
                        if (TestData1[i] != TestData2[i])
                        {
                            Diff12++;
                        }
                        if (TestData1[i] != TestData3[i])
                        {
                            Diff13++;
                        }
                    }

                    // Reading the maximum value
                    for (int i = 0; i < (DataSize + CodeSize); i++)
                    {
                        if (MaxCodeVal < TestData2[i])
                        {
                            MaxCodeVal = TestData2[i];
                        }
                    }

                    // If there is not difference, this test result is good,
                    // otherwise the test result is bad
                    if (Diff13 == TestErrCount)
                    {
                        if (Diff12 == 0)
                        {
                            ResultGood++;
                        }
                        else
                        {
                            ResultBad++;
                        }
                    }
                    else
                    {
                        ResultFailure++;
                    }

                }
                else
                {
                    ResultFalse++;
                }


                // Printing the test progress
                if ((TestIterations / 100) > 0)
                {
                    if ((TestI % (TestIterations / 100)) == 0)
                    {
                        Console.WriteLine("Progress: " + (TestI / (TestIterations / 100)) + "%");
                    }
                }
                else
                {
                    Console.WriteLine("Progress: " + TestI + "/" + TestIterations);
                }
            }

            // Printing the test results
            Console.WriteLine("Maximum existing value: " + MaxCodeVal.ToString());
            Console.WriteLine("Good: " + ResultGood);
            Console.WriteLine("Bad: " + ResultBad);
            Console.WriteLine("False: " + ResultFalse);
            Console.WriteLine("Failed: " + ResultFailure);
            Console.WriteLine("Total: " + (ResultFalse + ResultGood + ResultBad + ResultFailure));
            Console.ReadLine();
        }
    }
}

I tested with a few another data sizes, code sizes and number of bits. in every case all tests passed, so I assume, that the issue is solved now.

[andrzejlisek]

I recently read, that there is third way of Reed-Solomon code working:
If number of code symbols equals to CodeSize and error location are not known, the RS code can detect errors greater than CodeSize/2 up to CodeSize, but cannot correct errors in such case.

How I have to understand this information?

1. RS code detects only the fact that data sequence has uncorrectable errors?
2. RS code finds the error locations but does not correct (this gives information, which elements of data sequence must be retransmitted)?

I ran the test code with following parameters:

int NumOfBits = 4;
int DataSize = 10;
int CodeSize = 4;
int TestErrCount = 4;
bool KnownErrors = false;

The false return values was in about 2/3 of test cases. The remaining cases gave bad result, so the RSD.Decode returned true but data sequence differs than original (as I expected).

I changed value size to 8 bits, other parameters are the same:

int NumOfBits = 8;
int DataSize = 10;
int CodeSize = 4;
int TestErrCount = 4;
bool KnownErrors = false;

In this case, about 1/1000 of test cases as bad instead of false. I expected, that all cases will be false.

Now, I extended the data and code sizes:

int NumOfBits = 8;
int DataSize = 223;
int CodeSize = 32;
int TestErrCount = 32;
bool KnownErrors = false;

In the above parameters, the test took much more time, but all cases returned false as I expected.

The test conclusion seems be: If the number of erroneous values are equal to CodeSize, there is no guarantee to get information that sequence has incorectable errors. Why? Is there another bug in my code?