Reed Solomon error correction (success), Visual Basic

Reed Solomon error correction (success)

Option Infer On

Imports System
Imports System.Collections.Generic
Imports System.Linq
Imports System.Text.RegularExpressions
Imports System.Text
Imports Microsoft.VisualBasic

Namespace Rextester
    Public Module Program
        Public Sub Main(args() As String)
            Dim GaloisField As New GenericGF(285, 256, 0)
            Dim rsEncoder As New ReedSolomonEncoder(GaloisField)
            Dim message As Integer() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
            Dim chars As Char() = "Test message"
            For i As Integer = 0 To 11
                message(i) = Asc(chars(i))
            Next
            rsEncoder.encode(message, 12)
            Dim messageCodewords As String = "["
            For i As Integer = 0 To 23
                messageCodewords &= message(i) & ", "
            Next
            messageCodewords = messageCodewords.Substring(0, messageCodewords.Length - 2)
            messageCodewords &= "]"
            Console.WriteLine("Message Codeword: " & messageCodewords & VbNewLine)
            message(1) = 12
            message(3) = 9
            message(5) = 65
            message(7) = 1
            message(10) = 50
            message(18) = 25
            ' message(20) = 0
            messageCodewords = "["
            For i As Integer = 0 To 23
                messageCodewords &= message(i) & ", "
            Next
            messageCodewords = messageCodewords.Substring(0, messageCodewords.Length - 2)
            messageCodewords &= "]"
            Console.WriteLine("Message Codeword (with six errors): " & messageCodewords & VbNewLine)
            Dim rsDecoder As New ReedSolomonDecoder(GaloisField)
            If rsDecoder.decode(message, 12) Then
            messageCodewords = "["
            For i As Integer = 0 To 23
                messageCodewords &= message(i) & ", "
            Next
            messageCodewords = messageCodewords.Substring(0, messageCodewords.Length - 2)
            messageCodewords &= "]"
            Console.WriteLine("Decoded message: " & messageCodewords)
            Else
            Console.WriteLine("Too many errors")
            End If
        End Sub
    End Module
End Namespace

Public NotInheritable Class GenericGF
    Public Shared AZTEC_DATA_12 As New GenericGF(&H1069, 4096, 1)
    Public Shared AZTEC_DATA_10 As New GenericGF(&H409, 1024, 1)
    Public Shared AZTEC_DATA_6 As New GenericGF(&H43, 64, 1)
    Public Shared AZTEC_PARAM As New GenericGF(&H13, 16, 1)
    Public Shared QR_CODE_FIELD_256 As New GenericGF(&H11D, 256, 0)
    Public Shared DATA_MATRIX_FIELD_256 As New GenericGF(&H12D, 256, 1)
    Public Shared AZTEC_DATA_8 As GenericGF = DATA_MATRIX_FIELD_256
    Public Shared MAXICODE_FIELD_64 As GenericGF = AZTEC_DATA_6

Private expTable As Integer()
    Private logTable As Integer()
    Private m_zero As GenericGFPoly
    Private m_one As GenericGFPoly
    Private ReadOnly m_size As Integer
    Private ReadOnly primitive As Integer
    Private ReadOnly m_generatorBase As Integer

Public Sub New(primitive As Integer, size As Integer, genBase As Integer)
        Me.primitive = primitive
        Me.m_size = size
        Me.m_generatorBase = genBase

expTable = New Integer(size - 1) {}
        logTable = New Integer(size - 1) {}
        Dim x As Integer = 1
        For i As Integer = 0 To size - 1
            expTable(i) = x
            x <<= 1
            If x >= size Then
                x = x Xor primitive
                x = x And size - 1
            End If
        Next
        For i As Integer = 0 To size - 2
            logTable(expTable(i)) = i
        Next
        m_zero = New GenericGFPoly(Me, New Integer() {0})
        m_one = New GenericGFPoly(Me, New Integer() {1})
    End Sub

Friend ReadOnly Property Zero() As GenericGFPoly
        Get
            Return m_zero
        End Get
    End Property

Friend ReadOnly Property One() As GenericGFPoly
        Get
            Return m_one
        End Get
    End Property

Friend Function buildMonomial(degree As Integer, coefficient As Integer) As GenericGFPoly
        If degree < 0 Then
            Throw New ArgumentException()
        End If
        If coefficient = 0 Then
            Return m_zero
        End If
        Dim coefficients As Integer() = New Integer(degree) {}
        coefficients(0) = coefficient
        Return New GenericGFPoly(Me, coefficients)
    End Function

Friend Shared Function addOrSubtract(a As Integer, b As Integer) As Integer
        Return a Xor b
    End Function

Friend Function exp(a As Integer) As Integer
        Return expTable(a)
    End Function

Friend Function log(a As Integer) As Integer
        If a = 0 Then
            Throw New ArgumentException()
        End If
        Return logTable(a)
    End Function

Friend Function inverse(a As Integer) As Integer
        If a = 0 Then
            Throw New ArithmeticException()
        End If
        Return expTable(m_size - logTable(a) - 1)
    End Function

Friend Function multiply(a As Integer, b As Integer) As Integer
        If a = 0 OrElse b = 0 Then
            Return 0
        End If
        Return expTable((logTable(a) + logTable(b)) Mod (m_size - 1))
    End Function

Public ReadOnly Property Size() As Integer
        Get
            Return m_size
        End Get
    End Property

Public ReadOnly Property GeneratorBase() As Integer
        Get
            Return m_generatorBase
        End Get
    End Property

Public Overrides Function ToString() As [String]
        Return "GF(0x" & primitive.ToString("X") & ","c & m_size & ")"c
    End Function
End Class

Friend NotInheritable Class GenericGFPoly
    Private ReadOnly field As GenericGF
    Private ReadOnly m_coefficients As Integer()

Friend Sub New(field As GenericGF, coefficients As Integer())
        If coefficients.Length = 0 Then
            Throw New ArgumentException()
        End If
        Me.field = field
        Dim coefficientsLength As Integer = coefficients.Length
        If coefficientsLength > 1 AndAlso coefficients(0) = 0 Then
            Dim firstNonZero As Integer = 1
            While firstNonZero < coefficientsLength AndAlso coefficients(firstNonZero) = 0
                firstNonZero += 1
            End While
            If firstNonZero = coefficientsLength Then
                Me.m_coefficients = New Integer() {0}
            Else
                Me.m_coefficients = New Integer(coefficientsLength - firstNonZero - 1) {}
                Array.Copy(coefficients, firstNonZero, Me.m_coefficients, 0, Me.m_coefficients.Length)
            End If
        Else
            Me.m_coefficients = coefficients
        End If
    End Sub

Friend ReadOnly Property Coefficients() As Integer()
        Get
            Return m_coefficients
        End Get
    End Property

Friend ReadOnly Property Degree() As Integer
        Get
            Return m_coefficients.Length - 1
        End Get
    End Property

Friend ReadOnly Property isZero() As Boolean
        Get
            Return m_coefficients(0) = 0
        End Get
    End Property

Friend Function getCoefficient(degree As Integer) As Integer
        Return m_coefficients(m_coefficients.Length - 1 - degree)
    End Function

Friend Function evaluateAt(a As Integer) As Integer
        Dim result As Integer = 0
        If a = 0 Then
            Return getCoefficient(0)
        End If
        Dim size As Integer = m_coefficients.Length
        If a = 1 Then
            For Each coefficient In m_coefficients
                result = GenericGF.addOrSubtract(result, coefficient)
            Next
            Return result
        End If
        result = m_coefficients(0)
        For i As Integer = 1 To size - 1
            result = GenericGF.addOrSubtract(field.multiply(a, result), m_coefficients(i))
        Next
        Return result
    End Function

Friend Function addOrSubtract(other As GenericGFPoly) As GenericGFPoly
        If Not field.Equals(other.field) Then
            Throw New ArgumentException("GenericGFPolys do not have same GenericGF field")
        End If
        If isZero Then
            Return other
        End If
        If other.isZero Then
            Return Me
        End If

Dim smallerCoefficients As Integer() = Me.m_coefficients
        Dim largerCoefficients As Integer() = other.coefficients
        If smallerCoefficients.Length > largerCoefficients.Length Then
            Dim temp As Integer() = smallerCoefficients
            smallerCoefficients = largerCoefficients
            largerCoefficients = temp
        End If
        Dim sumDiff As Integer() = New Integer(largerCoefficients.Length - 1) {}
        Dim lengthDiff As Integer = largerCoefficients.Length - smallerCoefficients.Length
        Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff)

For i As Integer = lengthDiff To largerCoefficients.Length - 1
            sumDiff(i) = GenericGF.addOrSubtract(smallerCoefficients(i - lengthDiff), largerCoefficients(i))
        Next

Return New GenericGFPoly(field, sumDiff)
    End Function

Friend Function multiply(other As GenericGFPoly) As GenericGFPoly
        If Not field.Equals(other.field) Then
            Throw New ArgumentException("GenericGFPolys do not have same GenericGF field")
        End If
        If isZero OrElse other.isZero Then
            Return field.Zero
        End If
        Dim aCoefficients As Integer() = Me.m_coefficients
        Dim aLength As Integer = aCoefficients.Length
        Dim bCoefficients As Integer() = other.coefficients
        Dim bLength As Integer = bCoefficients.Length
        Dim product As Integer() = New Integer(aLength + bLength - 2) {}
        For i As Integer = 0 To aLength - 1
            Dim aCoeff As Integer = aCoefficients(i)
            For j As Integer = 0 To bLength - 1
                product(i + j) = GenericGF.addOrSubtract(product(i + j), field.multiply(aCoeff, bCoefficients(j)))
            Next
        Next
        Return New GenericGFPoly(field, product)
    End Function

Friend Function multiply(scalar As Integer) As GenericGFPoly
        If scalar = 0 Then
            Return field.Zero
        End If
        If scalar = 1 Then
            Return Me
        End If
        Dim size As Integer = m_coefficients.Length
        Dim product As Integer() = New Integer(size - 1) {}
        For i As Integer = 0 To size - 1
            product(i) = field.multiply(m_coefficients(i), scalar)
        Next
        Return New GenericGFPoly(field, product)
    End Function

Friend Function multiplyByMonomial(degree As Integer, coefficient As Integer) As GenericGFPoly
        If degree < 0 Then
            Throw New ArgumentException()
        End If
        If coefficient = 0 Then
            Return field.Zero
        End If
        Dim size As Integer = m_coefficients.Length
        Dim product As Integer() = New Integer(size + (degree - 1)) {}
        For i As Integer = 0 To size - 1
            product(i) = field.multiply(m_coefficients(i), coefficient)
        Next
        Return New GenericGFPoly(field, product)
    End Function

Friend Function divide(other As GenericGFPoly) As GenericGFPoly()
        If Not field.Equals(other.field) Then
            Throw New ArgumentException("GenericGFPolys do not have same GenericGF field")
        End If
        If other.isZero Then
            Throw New ArgumentException("Divide by 0")
        End If

Dim quotient As GenericGFPoly = field.Zero
        Dim remainder As GenericGFPoly = Me

Dim denominatorLeadingTerm As Integer = other.getCoefficient(other.Degree)
        Dim inverseDenominatorLeadingTerm As Integer = field.inverse(denominatorLeadingTerm)

While remainder.Degree >= other.Degree AndAlso Not remainder.isZero
            Dim degreeDifference As Integer = remainder.Degree - other.Degree
            Dim scale As Integer = field.multiply(remainder.getCoefficient(remainder.Degree), inverseDenominatorLeadingTerm)
            Dim term As GenericGFPoly = other.multiplyByMonomial(degreeDifference, scale)
            Dim iterationQuotient As GenericGFPoly = field.buildMonomial(degreeDifference, scale)
            quotient = quotient.addOrSubtract(iterationQuotient)
            remainder = remainder.addOrSubtract(term)
        End While

Return New GenericGFPoly() {quotient, remainder}
    End Function

Public Overrides Function ToString() As [String]
        Dim result As New StringBuilder(8 * Degree)
        For degree__1 As Integer = Degree To 0 Step -1
            Dim coefficient As Integer = getCoefficient(degree__1)
            If coefficient <> 0 Then
                If coefficient < 0 Then
                    result.Append(" - ")
                    coefficient = -coefficient
                Else
                    If result.Length > 0 Then
                        result.Append(" + ")
                    End If
                End If
                If degree__1 = 0 OrElse coefficient <> 1 Then
                    Dim alphaPower As Integer = field.log(coefficient)
                    If alphaPower = 0 Then
                        result.Append("1"c)
                    ElseIf alphaPower = 1 Then
                        result.Append("a"c)
                    Else
                        result.Append("a^")
                        result.Append(alphaPower)
                    End If
                End If
                If degree__1 <> 0 Then
                    If degree__1 = 1 Then
                        result.Append("x"c)
                    Else
                        result.Append("x^")
                        result.Append(degree__1)
                    End If
                End If
            End If
        Next
        Return result.ToString()
    End Function
End Class

Public NotInheritable Class ReedSolomonEncoder
    Private ReadOnly field As GenericGF
    Private ReadOnly cachedGenerators As IList(Of GenericGFPoly)

Public Sub New(field As GenericGF)
        Me.field = field
        Me.cachedGenerators = New List(Of GenericGFPoly)()
        cachedGenerators.Add(New GenericGFPoly(field, New Integer() {1}))
    End Sub

Private Function buildGenerator(degree As Integer) As GenericGFPoly
        If degree >= cachedGenerators.Count Then
            Dim lastGenerator = cachedGenerators(cachedGenerators.Count - 1)
            For d As Integer = cachedGenerators.Count To degree
                Dim nextGenerator = lastGenerator.multiply(New GenericGFPoly(field, New Integer() {1, field.exp(d - 1 + field.GeneratorBase)}))
                cachedGenerators.Add(nextGenerator)
                lastGenerator = nextGenerator
            Next
        End If
        Return cachedGenerators(degree)
    End Function

Public Sub encode(toEncode As Integer(), ecBytes As Integer)
        If ecBytes = 0 Then
            Throw New ArgumentException("No error correction bytes")
        End If
        Dim dataBytes = toEncode.Length - ecBytes
        If dataBytes <= 0 Then
            Throw New ArgumentException("No data bytes provided")
        End If

Dim generator = buildGenerator(ecBytes)
        Dim infoCoefficients = New Integer(dataBytes - 1) {}
        Array.Copy(toEncode, 0, infoCoefficients, 0, dataBytes)

Dim info = New GenericGFPoly(field, infoCoefficients)
        info = info.multiplyByMonomial(ecBytes, 1)

Dim remainder = info.divide(generator)(1)
        Dim coefficients = remainder.Coefficients
        Dim numZeroCoefficients = ecBytes - coefficients.Length
        For i = 0 To numZeroCoefficients - 1
            toEncode(dataBytes + i) = 0
        Next

Array.Copy(coefficients, 0, toEncode, dataBytes + numZeroCoefficients, coefficients.Length)
    End Sub
End Class

Public NotInheritable Class ReedSolomonDecoder
    Private ReadOnly field As GenericGF

Public Sub New(field As GenericGF)
        Me.field = field
    End Sub

Public Function decode(received As Integer(), twoS As Integer) As Boolean
        Dim poly = New GenericGFPoly(field, received)
        Dim syndromeCoefficients = New Integer(twoS - 1) {}
        Dim noError = True
        For i = 0 To twoS - 1
            Dim eval = poly.evaluateAt(field.exp(i + field.GeneratorBase))
            syndromeCoefficients(syndromeCoefficients.Length - 1 - i) = eval
            If eval <> 0 Then
                noError = False
            End If
        Next
        If noError Then
            Return True
        End If
        Dim syndrome = New GenericGFPoly(field, syndromeCoefficients)

Dim sigmaOmega = runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS)
        If sigmaOmega Is Nothing Then
            Return False
        End If

Dim sigma = sigmaOmega(0)
        Dim errorLocations = findErrorLocations(sigma)
        If errorLocations Is Nothing Then
            Return False
        End If

Dim omega = sigmaOmega(1)
        Dim errorMagnitudes = findErrorMagnitudes(omega, errorLocations)
        For i = 0 To errorLocations.Length - 1
            Dim position = received.Length - 1 - field.log(errorLocations(i))
            If position < 0 Then
                Return False
            End If
            received(position) = GenericGF.addOrSubtract(received(position), errorMagnitudes(i))
        Next

Return True
    End Function

Friend Function runEuclideanAlgorithm(a As GenericGFPoly, b As GenericGFPoly, R__1 As Integer) As GenericGFPoly()
        If a.Degree < b.Degree Then
            Dim temp As GenericGFPoly = a
            a = b
            b = temp
        End If

Dim rLast As GenericGFPoly = a
        Dim r__2 As GenericGFPoly = b
        Dim tLast As GenericGFPoly = field.Zero
        Dim t As GenericGFPoly = field.One

While r__2.Degree >= R__1 / 2
            Dim rLastLast As GenericGFPoly = rLast
            Dim tLastLast As GenericGFPoly = tLast
            rLast = r__2
            tLast = t

If rLast.isZero Then
                Return Nothing
            End If
            r__2 = rLastLast
            Dim q As GenericGFPoly = field.Zero
            Dim denominatorLeadingTerm As Integer = rLast.getCoefficient(rLast.Degree)
            Dim dltInverse As Integer = field.inverse(denominatorLeadingTerm)
            While r__2.Degree >= rLast.Degree AndAlso Not r__2.isZero
                Dim degreeDiff As Integer = r__2.Degree - rLast.Degree
                Dim scale As Integer = field.multiply(r__2.getCoefficient(r__2.Degree), dltInverse)
                q = q.addOrSubtract(field.buildMonomial(degreeDiff, scale))
                r__2 = r__2.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale))
            End While

t = q.multiply(tLast).addOrSubtract(tLastLast)

If r__2.Degree >= rLast.Degree Then
                Return Nothing
            End If
        End While

Dim sigmaTildeAtZero As Integer = t.getCoefficient(0)
        If sigmaTildeAtZero = 0 Then
            Return Nothing
        End If

Dim inverse As Integer = field.inverse(sigmaTildeAtZero)
        Dim sigma As GenericGFPoly = t.multiply(inverse)
        Dim omega As GenericGFPoly = r__2.multiply(inverse)
        Return New GenericGFPoly() {sigma, omega}
    End Function

Private Function findErrorLocations(errorLocator As GenericGFPoly) As Integer()
        Dim numErrors As Integer = errorLocator.Degree
        If numErrors = 1 Then
            Return New Integer() {errorLocator.getCoefficient(1)}
        End If
        Dim result As Integer() = New Integer(numErrors - 1) {}
        Dim e As Integer = 0
        Dim i As Integer = 1
        While i < field.Size AndAlso e < numErrors
            If errorLocator.evaluateAt(i) = 0 Then
                result(e) = field.inverse(i)
                e += 1
            End If
            i += 1
        End While
        If e <> numErrors Then
            Return Nothing
        End If
        Return result
    End Function

Private Function findErrorMagnitudes(errorEvaluator As GenericGFPoly, errorLocations As Integer()) As Integer()
        Dim s As Integer = errorLocations.Length
        Dim result As Integer() = New Integer(s - 1) {}
        For i As Integer = 0 To s - 1
            Dim xiInverse As Integer = field.inverse(errorLocations(i))
            Dim denominator As Integer = 1
            For j As Integer = 0 To s - 1
                If i <> j Then
                    Dim term As Integer = field.multiply(errorLocations(j), xiInverse)
                    Dim termPlus1 As Integer = If((term And &H1) = 0, term Or 1, term And Not 1)
                    denominator = field.multiply(denominator, termPlus1)
                End If
            Next
            result(i) = field.multiply(errorEvaluator.evaluateAt(xiInverse), field.inverse(denominator))
            If field.GeneratorBase <> 0 Then
                result(i) = field.multiply(result(i), xiInverse)
            End If
        Next
        Return result
    End Function
End Class


run \| edit \| history \| help	0