纠突发错误编码.

Presentation on theme: "纠突发错误编码."— Presentation transcript:

1 纠突发错误编码

2 突发信道 短波、散射、有线信道；磁记录信道等，突发错误或突发错误与随机错误并存 突发信道的最好的差错控制方法是ARQ

3 以多项式表示错误图样：在长为n的码字内，长度不大于b的突发错误图样是：
E(x)=xib(x) i=0,1,…,n-b, deg(b(x)) ≤b-1 循环（首尾相接）突发错误图样： E(x)=xib(x) i=0,1,…,n-1 (mod xn-1) 任何一个[n,k]分组码，若能纠正码组中长度不大于b的所有突发错误图样，则称b为该码的纠突发能力。

4 纠突发能力和n，k关系 一个q进制[n, k]线性分组码，若要发现（或检测）所有长度≤b的突发错误，其充要条件是需要b个校验元。
任何[n,k]线性码，能发现所有长度≤n-k的突发错误。

5 纠突发能力和n，k关系 一个q进制[n, k]线性码，若
(1)要纠正所有长度≤b的突发，则至少需要2b个校验元，即n-k ≥2b； (Rieger限，必要条件) (2)要纠正所有长度≤b，且同时发现所有长度≤d, (d≥b)的突发，至少需要b+d个校验元，即n-k ≥b+d 若[n, k]线性码要具有能纠正任何长度≤b的突发错误能力，其充要条件是任何两个长度≤b的突发的任意组合不能作为一个码字。

6 纠突发能力和n，k关系 具有纠突发能力为b的[n,k]线性码，能检测任何两个长度≤b的突发错误的所有组合，反之亦然。
若码的纠错能力达到R限，则该码为R意义下的最佳就突发错误码，简称R最佳码。 Z=2b/(n-k) s=n-k-2b

7 纠突发能力和n，k关系 有最小距离为d的[n,k]循环码，能检测每个长度≤bi (i=1,2,…,T)的所有T个突发，其中
有最小距离为d的[n,k]循环码，能同时纠正p个突发 错误，且每个突发长度为bi，i=1,2,…,T，其中

8 对任何一个[n, k, d≥3]二进制循环码，纠突发能力 对大部分二进制[n, k, d≥3]BCH码，纠突发能力b满足

9 Fire码 设g1(x)生成一个纠突发能力为b的[n1,k1]循环码，p(x)的周期为a，且deg(p(x)) ≥b,(p(x),g1(x))=1，则由g(x)=g1(x)p(x)生成的循环码，码长n=n1a,能纠正长度≤b的所有突发错误。 由g(x)=(x2b-1+1)p(x)生成的[n,n-2b-m+1]的循环码称为fire码。能纠正码字内长度≤b的所有单个突发错误。码长n=LCM(e,2b-1)，e是p(x)的周期，且deg(p(x))=m≥b,(p(x),x2b-1+1)=1 Z=2b/(3b+1)

10 RS码 GF(qm)上的能纠正t个错误的[qm-1,qm-1-2t]RS码，能纠正GF(qm)上的长度≤t的突发错误，Z=1
[n,k]码，n=sm，定义m个连续码元为一段，一个长度≤lm并且局限于连续l段的突发，定义为一个定段突发错误。 若采用GF(q)表示每个码元，可纠正长度≤m的t个定段突发错误，亦可纠正长度≤mt的单个定段突发错误

11 ai,n-1 ai,n-2 ... ai,n-k ai,n-k-1 … ai,1 ai,0
交错码与乘积码 思路：将突发错误离散成随机错误 交错码：[n,k] →[ni,ki]，i：交错次数或交错度 若行码能纠正t个随机错误或b长突发错误，则[ni,ki]交错码能纠正所有长度≤it或≤ib的突发 若行码能纠正t个随机错误，则[ni,ki]交错码能纠正t个长度≤i的突发错误或纠正长度≤it的单个突发 a1,n-1 a1,n a1,n-k a1,n-k-1 … a1,1 a1,0 a2,n-1 a2,n a2,n-k a2,n-k-1 … a2,1 a2,0 …… ai,n-1 ai,n ai,n-k ai,n-k-1 … ai,1 ai,0

12 交错码与乘积码 乘积码(二维码)：[n1,k1],[n2,k2] →[n1n2,k1k2]
b≤max(b1n2, b2n1), b ≤max(t1n2,t2n1), t ≤(d1d2-1)/2

13 级联码 外编码器 GF(2k)上的 [N,K]码 内编码器 GF(2)上的 [n,k]码 信道 外译码器 GF(2k)上的 [N,K]码
输入 [Nn,Kk]级联码编码器 信道 外译码器 GF(2k)上的 [N,K]码 内译码器 GF(2)上的 [n,k]码 输出 [Nn,Kk]级联码译码器