REED-SOLOMON CODES

数字通信系统模型

纠错码的发展概况 通信的数学理论，Shannon(1948) 汉明码，Hamming (1950) 级连码，Forney(1966) 卷积码及有效译码, (60年代) RS码及BCH码的有效译码(60年代) TCM，Ungerboeck(1982),Forney(1984) Turbo码，Berrou(1993) LDPC 码，Gallager(1963),Macky(1996) 空时编码,Tarokh(2000) 协作与网络编码(2000;2002)

码距与检错和纠错能力的关系

二进制本源BCH码 对于任意正整数m(m≥3)和t(t< )，存在GF(2)具有 如下参数的二进制本原BCH码(n, k) ： 分组长度 奇偶校验位的数目 最小距离 该码字(n, k)能够纠正t个或少于t个差错的任意组合。

非二进制本源BCH码 存在 具有如下参数的非二进制本原BCH码： 分组长度 奇偶校验位的数目 最小距离

Reed-solomon码 m = 1 的q进制BCH码是q进制BCH码中最重要 的一个子类 分组长度 奇偶校验位的数目 最小距离

BCH 和 RS 二进制BCH 非二进制RS RS码

编码的最小码距直接关系到这种码的检错和纠错能力

解调 判决 译码 硬判决译码 接收端解调器将含有噪声的信号用匹配滤波器硬判 决，得到0或者1，这就是接收序列r 处理这种硬判决接收序列的译码算法叫做硬判决译 码 硬判决丢失了接受信号中含有的一些信息，影响译 码性能 解调 判决 译码

解调 译码 软判决译码 若解调器对信号没有量化或量化为多于两个电平， 得到软判决接收序列。利用软判决接收序列进行译 码叫做软判决译码 一般比硬判决译码多3dB增益 解调 译码

主要译码算法 hard-decision decoding (HDD): Berlekamp-Messay algorithm (BMA) iBM, RiBM, Eucild soft-decision decoding: KV GMD ->BGMD Chase -> Low-complexity chase (LCC)

RiBM 信码 生成多项式 编码 发送码字 过信道加噪声 c(x) + e(x) 接收码字

RIBM 校验子syndrome V是码字错误个数，可见校验的值只与错误位置和值有关， 若传输无错，校验子为零

RiBM 定义错误位置Xk 和错误值 Yk : 校验子和Xk， Yk

RiBM 定义错误位置多项式 错误估值多项式 求解关键方程 Forney算法

algebraic soft-decision decoding multiplicity assignment interpolation factorization

LCC 译码过程

Multiplicity Assignment The error-correcting capacity and complexity of ASD algorithms are mainly determined by the multiplicity assignment step. KV BGMD LCC

Multiplicity Assignment KV multiplicity assignment BGMD multiplicity assignment

LCC multiplicity assignment In the LCC multiplicity assignment scheme the reliability of each code position is first determined by the log-likelihood ratio (LLR). Here and are the most likely and second most likely symbols transmitted in the j-th position, respectively.

LCC multiplicity assignment η<n-k most unreliable code positions While other n-η code positions

Modified-LCC multiplicity assignment a modified LCC (MLCC) decoding is proposed by adding erasures to the test vectors. With the same η , the proposed algorithm can achieve much better performance than the original LCC decoding. Implementation of ASD algorithms for a long RS code over the EPR4 channel with 100% AWGN. BCJR algorithm is used as the channel detector to output the reliability of each received bit.

Modified-LCC multiplicity assignment

Re-encoding and Coordinate Transformation The complexity of the ASD algorithms can be significantly reduced by applying the re-encoding and coordinate transformation k most reliable code position η most unreliable code position rest n-k-η most reliable code position

Re-encoding and Coordinate Transformation Re-encoder or erasure-only decoder

Re-encoder and Coordinate Transaction

Re-encoder and Coordinate Transaction

interpolation

interpolation

Backward interpolation for LCC decoding

Interpolation Backward interpolation for LCC decoding Unified Backward-forward LCC Interpolation Reduced-complexity Multi-interpolator Scheme for the LCC decoding

Backward interpolation for LCC decoding

Unified Backward-forward LCC Interpolation

Reduced-complexity Multi-interpolator Scheme for the LCC decoding

Reduced-complexity Multi-interpolator Scheme for the LCC decoding

Comparison with Backward-forward and unified Backward-forward whole unified(×4) Proposed unified for-only-back-ward GF Mult. 14 21 84 59 GF Adder 12 19 76 39 GF Inv. 1 4 Mux (bit) 6q 15q 60q 77q Ram (bit) 4(n – k + 1)q 16(n – k + 1)q Reg.(bit) 16q 27q 108q 117q iterations (n - k) + 2*(2^η - 1) (n - k) + (2^η - 1) (n - k) + (2^η/4 - 1) Clks of each iter. dx + 4 dx + 5

Factorization

Factorization-Free

Factorization-Free

Hard-Decision based LCC

Hard-Decision based LCC

几个重要性能指标 coding gain FER or BER

几个重要性能指标 Throughput Systematical clock Latency Critical path Area : the number of XOR gates Power consumption