python
from itertools import combinations
MOD = 7
X_VALUES = list(range(6))
N = 6
K = 3
def evaluate(coeff, x):
"""
计算P(x)，系数从低次到高次排列。
例如(2,3,1)代表2+3x+x^2。
"""
result = 0
for a in reversed(coeff):
result = (result*x + a) % MOD
return result
def encode(message):
"""
3个有限域符号 -> 6个编码符号
"""
if len(message) != K:
raise ValueError("消息必须恰好包含3个符号")
if any(not (0 <= v < MOD) for v in message):
raise ValueError("每个符号必须位于0到6之间")
return [
evaluate(message, x)
for x in X_VALUES
]
def multiply_linear(poly, root):
"""
将多项式poly乘以(x-root)，模7。
系数采用低次在前的形式。
"""
out = [0] * (len(poly) + 1)
for degree, value in enumerate(poly):
out[degree] = (
out[degree] - root*value
) % MOD
out[degree+1] = (
out[degree+1] + value
) % MOD
return out
def interpolate_three(points):
"""
通过3个互不相同的正确采样点，
恢复次数小于3的多项式系数。
"""
if len(points) != 3:
raise ValueError("必须提供3个采样点")
coeff = [0, 0, 0]
for i, (xi, yi) in enumerate(points):
basis = [1]
denominator = 1
for j, (xj, _) in enumerate(points):
if i == j:
continue
basis = multiply_linear(basis, xj)
denominator = (
denominator * (xi-xj)
) % MOD
inverse = pow(denominator, -1, MOD)
scale = yi * inverse % MOD
for d in range(K):
coeff[d] = (
coeff[d] + scale*basis[d]
) % MOD
return tuple(coeff)
def decode(received):
"""
Reed-Solomon (6,3) 教学版译码。
received为6个符号，每个值：
0..6 = 收到的符号
None = 已知位置擦除
选择3个未擦除的位置进行多项式插值，
检查候选多项式与全部未擦除值的差异。
若存在唯一候选且满足设计纠错半径，
则返回恢复的原始消息与码字。
注意：不负责验证实际错误是否超出保证范围。
"""
if len(received) != N:
raise ValueError("必须有6个接收位置")
known = [
(i, value)
for i, value in enumerate(received)
if value is not None
]
erasures = N - len(known)
if erasures > N-K:
return {
"status": "uncorrectable",
"reason": "已知位置擦除过多"
}
max_errors = (N-K-erasures)//2
candidates = set()
for subset in combinations(known, K):
coeff = interpolate_three(subset)
candidates.add(coeff)
valid = []
for coeff in candidates:
mismatches = sum(
evaluate(coeff, x) != value
for x, value in known
)
if mismatches <= max_errors:
valid.append((coeff, mismatches))
if len(valid) != 1:
return {
"status": "uncorrectable",
"reason": "无唯一的设计半径内候选"
}
coeff, errors = valid[0]
return {
"status": "decoded",
"message": list(coeff),
"codeword": encode(coeff),
"unknown_errors": errors,
"erasures": erasures
}
original = [2, 3, 1]
encoded = encode(original)
print("原始消息:", original)
print("六位码字:", encoded)
case_a = [2, 6, None, 6, None, None]
case_b = [2, 6, 4, 6, 2, 0]
case_c = [2, None, 4, 6, 2, 0]
case_d = [2, 0, 4, 6, 2, 0]
for title, case in [
("三个擦除", case_a),
("一个未知错误", case_b),
("一个错误加一个擦除", case_c),
("两个未知错误", case_d),
]:
print()
print(title)
print("接收:", case)
print("译码:", decode(case))
result = decode(case)
if title != "两个未知错误":
assert result["status"] == "decoded"
assert result["message"] == original
print()
print("所有保证范围内的测试通过")
python
PRIMITIVE_POLY = 0x11D
def gf256_add(a, b):
"""GF(2^8)中的加法就是异或。"""
return a ^ b
def gf256_mul(a, b):
"""
GF(2^8)乘法。
使用不可约多项式：
x^8 + x^4 + x^3 + x^2 + 1
对应0x11D。
"""
result = 0
for _ in range(8):
if b & 1:
result ^= a
b >>= 1
a <<= 1
if a & 0x100:
a ^= PRIMITIVE_POLY
return result & 0xFF
print("加法示例:")
print(
hex(gf256_add(0xB2, 0x6D))
)
print("乘法示例:")
print(
hex(gf256_mul(0xB2, 0x6D))
)
assert gf256_add(0xB2, 0xB2) == 0
assert gf256_mul(0xB2, 0) == 0
assert gf256_mul(0xB2, 1) == 0xB2
print("基本有限域运算测试通过")