REED-SOLOMON CODES.

Presentation on theme: "REED-SOLOMON CODES."— Presentation transcript:

1 REED-SOLOMON CODES

2 数字通信系统模型

3 纠错码的发展概况 通信的数学理论，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)

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

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

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

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

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

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

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

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

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

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

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

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

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

17 algebraic soft-decision decoding
multiplicity assignment interpolation factorization

18 LCC 译码过程

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

20 Multiplicity Assignment
KV multiplicity assignment BGMD multiplicity assignment

21 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.

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

23 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.

24 Modified-LCC multiplicity assignment

25 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

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

27 Re-encoder and Coordinate Transaction

28 Re-encoder and Coordinate Transaction

29 interpolation

30 interpolation

31 Backward interpolation for LCC decoding

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

33 Backward interpolation for LCC decoding

34 Unified Backward-forward LCC Interpolation

35 Reduced-complexity Multi-interpolator Scheme for the LCC decoding

36 Reduced-complexity Multi-interpolator Scheme for the LCC decoding

37 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

38 Factorization

39 Factorization-Free

40 Factorization-Free

41 Hard-Decision based LCC

42 Hard-Decision based LCC

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

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