通信工程 / 系统课时

用 RS 码恢复损坏的符号

用 RS 码恢复损坏的符号

当连续几个字节遭到破坏时,逐比特检测能发现异常,却未必能恢复原文。RS 码把字节当作符号,利用额外校验符号纠正损坏。本课用 5 字节消息和 4 字节校验构造短码字,分别模拟未知位置错误与已知位置擦除,验证恢复结果。

学习目标

  • 解释符号错误与擦除的区别,计算 RS 码的纠错上限。
  • 用 Python 对一个字节码字编码、注入损坏并恢复原消息。
  • 判断连续损坏何时可修复,知道如何验证和处理超限情况。

五字节消息需要多少冗余

在常用的 GF(28)GF(2^8) 上,一个 RS 符号就是一个 0~255 的字节。即使一个字节内翻转了多个比特,也只算一个符号错误;两个不同字节损坏,才算两个符号错误。

以缩短的 RS(9,5) 为例:5 个数据符号追加 4 个校验符号,得到 9 字节码字,码率为 5/9≈0.5565/9\approx0.556。设未知损坏位置的符号错误数为 ee,已知位置但无法信任其取值的擦除数为 vv,保证恢复的条件是:

2e+v≤n−k=42e+v\le n-k=4
未知错误 ee 已知擦除 vv 消耗的校验能力 2e+v2e+v 是否在保证范围
2 0 4 是
0 4 4 是
1 2 4 是
3 0 6 否

这里的“否”表示不能保证正确解码,不等于每种数据都会报错。RS(9,5) 的最小符号距离为 5,因此定位一个未知错误需要的冗余,相当于恢复两个位置已知的擦除。

为什么连续擦除更容易恢复

假设九个符号从 0 编号到 8:前五个位置是消息 HELLO,后四个是校验字节。若位置 1、2 连续受损,接收端不知道位置,按 2 个错误处理;若位置 1~4 都损坏,但下层已经标出这四个位置,则按 4 个擦除处理。这两种情况恰好都用完 4 个校验符号的预算。

RS(9,5) 的符号错误和连续擦除对比

擦除不是把字节改成零。零只是损坏值的占位,接收端还必须从包丢失标记、存储块错误记录等来源获得准确位置;如果没有这些位置信息,就必须按未知错误计算。

用 Python 复现编码与恢复

使用 Python 3.10~3.12,在可安装依赖的环境中执行 python -m pip install reedsolo==1.7.0。预期结果:命令以退出码 0 结束,随后可正常导入 reedsolo;首次安装与已安装时的 pip 提示会不同。以下示例使用该版本的 RSCodec,参数 4 表示每个码字添加 4 个校验符号。

python
from reedsolo import RSCodec

codec = RSCodec(4)
message = b"HELLO"
encoded = bytes(codec.encode(message))

# 两处未知位置的错误:修改数值但不告知译码器位置
damaged = bytearray(encoded)
for pos in (1, 2):
    damaged[pos] ^= 0x5A
data_a, fixed_a, pos_a = codec.decode(bytes(damaged))

# 四处连续擦除:数值不可用,但位置由下层明确提供
erasures = [1, 2, 3, 4]
missing = bytearray(encoded)
for pos in erasures:
    missing[pos] = 0
data_b, fixed_b, pos_b = codec.decode(
    bytes(missing), erase_pos=erasures
)

assert bytes(data_a) == message
assert bytes(data_b) == message
print("码字长度:", len(encoded))
print("未知错误:", bytes(data_a).decode(), sorted(pos_a))
print("连续擦除:", bytes(data_b).decode(), sorted(pos_b))
print("校验结果:", codec.check(bytes(fixed_a)), codec.check(bytes(fixed_b)))

预期输出:

text
码字长度: 9
未知错误: HELLO [1, 2]
连续擦除: HELLO [1, 2, 3, 4]
校验结果: [True] [True]

decode 返回恢复的数据、恢复后的完整码字和被修正的位置;check 返回每个码块的校验状态,因此单块结果是 [True],不是单个布尔值。索引从 0 起算,包含数据符号和校验符号。

怎样判定恢复成功与失败

译码器先根据接收码字计算综合症;若存在异常,结合已知擦除位置定位损坏符号,再求出修正值,最后重新检查码字的校验关系。本例两组损坏分别满足 2×2=42\times2=4 和 4=44=4,所以能恢复 HELLO。

在工程实现中应按以下顺序检查:

  1. 按码字统计:RS(9,5) 的每 9 字节单独计数,不把两个码字的冗余合并;超出 2e+v≤42e+v\le4 时不能承诺恢复。
  2. 准确上报擦除位置:只有明确知道索引才能传入 erase_pos;不能仅因字节值为 0 就把它判成擦除。
  3. 处理异常和误纠:捕获 reedsolo.ReedSolomonError 并请求重传或报告不可恢复;超过设计纠错范围时,即便 check 通过也不保证恢复的是原文,关键数据应再用独立的 CRC 或摘要核对。
  4. 应对长突发损坏:若 4 个连续损坏字节的位置全未知,已超过单个 RS(9,5) 码字的 2 错误上限。可交替发送两个独立码字的符号,使连续 4 字节损坏分散为各码字最多 2 个错误;接收时须先解交织再译码,代价是额外缓冲时延。

RS 码的纠错额度按受损符号数而不是翻转比特数计算。能可靠标记擦除位置时,同样的 4 字节冗余可以恢复 4 个连续丢失的字节;位置未知时则只能保证纠正 2 个错误字节。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 RS 码恢复损坏的符号

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通