sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.47k stars 485 forks source link

Bug in Reed-Solomon error-erasure decoder #38918

Open luan-xiaokun opened 3 weeks ago

luan-xiaokun commented 3 weeks ago

Steps To Reproduce

A Reed-Solomon code RSC(n,k) is supposed to correct at most n - k erasures, while the following snippet shows that this error-erasure decoder does not work as expected.

F = GF(59)
n, k = 40, 12
C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
D = codes.decoders.GRSErrorErasureDecoder(C)
erasure_num = n - k  # work as expected if changed to values less than n - k

message = vector(F, list(range(1, k + 1)))
codeword = C.encode(message)
for i in range(erasure_num):
    codeword[i] = F.from_integer(1)
erasure = vector(GF(2), [1] * erasure_num + [0] * (n - erasure_num))
print(D.decode_to_message((codeword, erasure)))
# prints (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) instead of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Expected Behavior

The decoded message should be (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Actual Behavior

It prints (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) instead

Additional Information

I'm not very familiar with coding theory, but it seems that when there are n-k erasures and no errors, the decoding process is essentially solving a linear equation, and the following snippet works for my case.

received = vector(F, [w for i, w in enumerate(received) if erasure[i]])
vandermonde = matrix([[multipliers[i] * eval_points[i] ** j for j in range(cut)] for i in range(cut)])
decoded = vandermonde.inverse() * received

Environment

Checklist