Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Reed Solomon error correction (failure)
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 seven 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
png
VBA
I know all the veebeez!
exercicio 3
number from base 10 to base 2
3.1
5
ABS Cracker
pgcd def
VB checking whether a date is between 2 dates