Reed-Solomon Codes——RS纠错码

1. 引言

前序博客有：

• LDC——Locally Decodable Code

上图源自 How to send a self-correcting message (Hamming codes)。

Reed-Solomon Codes为基于block的纠错码，在数字通信和存储中有大量应用，在如下系统中用于纠错：

• 存储设备（包括磁带、光盘、DVD、条形码等）
• 无线或移动通信（包括手机、微波连接等）
• 卫星通信
• 数字电视/DVB
• 高速调制解调器，如ADSL、xDSL等

典型的系统如下图所示： Reed-Solomon encoder（编码器） 接收一块数字数据并添加额外的“冗余”位。数据在传输或存储过程中出现错误的原因有多种（如噪声或干扰，CD上的划痕等等）。 Reed-Solomon decoder（解码器） 会处理每个块，并试图纠正错误，恢复原始数据。

能纠正的错误类型和错误数量具体取决于Reed-Solomon码的特性。

2. Reed-Solomon码的特性

Reed-Solomon码为BCH码的子集，属于linear block码。

Reed-Solomon码定义为： R S ( n , k ) RS(n,k) RS(n,k) with s s s-bit symbols。

也就意味着：

• Reed-Solomon 编码器接收 k k k个data symbols，每个symbol对应有 s s s bits，然后添加parity symbols，最终获得长度为 n n n的symbol codeword。parity symbol的个数为 n − k n-k n−k个，每个parity symbol对应有 s s s bits。
• Reed-Solomon 解码器可纠正codeword中最多 t t t个symbol错误，其中 2 t = n − k 2t=n-k 2t=n−k。

对Reed-Solomon进行编解码所需的算力，与每个codeword内的parity symbols数量相关。更大的 t t t值以为这可纠正更多的错误，但是相比于 小 t t t 需要更多的算力。

已知symbol size为 s s s，则Reed-Solomon码的最大codeword length n n n为 n = 2 s − 1 n=2^s-1 n=2s−1。如对于8-bit symbol（ s = 8 s=8 s=8），其code最大长度为 255 255 255 bytes。

以下为典型的Reed-Solomon codeword（又名Systematic码，因为数据部分保持不变，仅附加了parity symbols）： 比如，流行的Reed-Solomon码 R S ( 255 , 223 ) RS(255,223) RS(255,223) with 8-bit symbols，每个codeword包含了255 code word bytes，其中223 bytes为数据，32 bytes为parity，有： n = 255 , k = 223 , s = 8 n=255,k=223,s=8 n=255,k=223,s=8 25 = 32 , t = 16 25=32, t=16 25=32,t=16

解码器可纠正code word中的任意16个symbol error，即codeword中的任意位置的最多16 bytes错误可被自动纠正。

2.1 缩短Reed-Solomon码

理论上Reed-Solomon码长度是可缩短的，通过在编码时将一定数量的data symbols设置为0，不传输这些为0的data symbols，然后在解码时重新插入为0的data symbols。 仍然以上面的 ( 255 , 223 ) (255,223) (255,223)码为例，可将其缩短为 ( 200 , 168 ) (200,168) (200,168)码，编码时的block内有168 data bytes，然后理论上增加55 zero bytes，创建出一个 ( 255 , 223 ) (255, 223) (255,223) codeword，但是实际仅需传输168 data bytes和32 parity bytes。

2.2 Symbol Errors

若单个symbol内有一个bit出错或者所有bit都错了时，则均为一个symbol error。

仍然以 R S ( 255 , 223 ) RS(255, 223) RS(255,223)为例，其可纠正 16 16 16个symbol errors，最差的情况是，有16 bit errors，每个bit错误发生在不同的symbol（byte），解码器纠正16 bit errors。最好的情况是，16个symbol内的所有bit都错了，此时解码器可纠正 16 × 8 16\times 8 16×8 bit errors。

Reed-Solomon码特别适于纠正burst errors（即所接收到的codeword内有a series of bits出错）。

2.3 解码

Reed-Solomon代数解码的过程中，可：

• 纠错
• 擦除：当已知错误symbol的位置时，可进行擦除。

解码器可最多纠正 t t t个symbol错误，或最多擦除 2 t 2t 2t个错误symbol。在数字通信系统中，擦除信息通常由解调器提供，即解调器会对其收到的symbols中可能 包含错误的symbol 进行“标记”。

当对codeword解码时，有以下3种可能：

• 1）若 2 s + r < 2 t 2s+r