华南理工大学：《现代编码理论与技术》课程教学资源（PPT课件讲稿）第一章 纠错码的基本概念

第一章纠错码概述 陆以勤

第一章 纠错码概述 陆以勤

在一切哲学那里，体系都是暂时的东西，但包含在体系 中的真正有价值的方法却可以长久地启发人心智、发人 深思。 我们所能有的最美好的经验是奥秘的经验，谁要是体验 不到它，谁要是不再有好奇心，也不再有惊讶的感觉， 他就无异于行尸走肉

在一切哲学那里，体系都是暂时的东西，但包含在体系 中的真正有价值的方法却可以长久地启发人心智、发人 深思。 我们所能有的最美好的经验是奥秘的经验，谁要是体验 不到它，谁要是不再有好奇心，也不再有惊讶的感觉， 他就无异于行尸走肉

一、什么叫纠错码 1.通信系统模型 信源信道联合编码 编码调制 密码编码 (conded modulation) r()= r=c+e 信源 m 信道 调 ss()+(② 解 信道 信源 金 源 编码 编码 制 调 译码 译码 信宿 压缩编码 检纠错 编码 噪声 信道：消息的传递途径，可以物 AWGN 理信道，也可以是一些处理过程， 如CD复制，硬盘，物流等 (additive white Gaussian noise)

一、什么叫纠错码 1. 通信系统模型 信 源 信源 编码 信道 编码 + 信道 译码 信源 译码 信 宿 u m c 噪声 e(t) r(t)= s(t)+e(t) ^ m ^ u 压缩编码 检纠错 编码 信道：消息的传递途径，可以物 理信道，也可以是一些处理过程， 如CD复制，硬盘，物流等 调 制 s(t) 解 调 r=c+e AWGN (additive white Gaussian noise) 信源信道联合编码 密码编码 编码调制 (conded modulation)

对于无线信道，还有调制和解调 信道模型 AWGN (additive white Gaussian noise) Xs=u QPSK 调制 a 交织器 a和a'为信道衰落因子，n和nP为两个独立分布的高斯噪声。 对于高斯白噪声信道，a和ak都为l。 2.纠错的两种方式： ARQ:Automatic Repeat Quest,自动重发请求，前提：检错 FEC:Forward error correct:前向纠错

对于无线信道，还有调制和解调 + + 交织器 + + Xs=u Xp1 Xp2 Xp u QPSK 调制 ap k + + xs k xp k cs k cp k as k ns k np k ys k yp k 信道模型 a s k和a p k为信道衰落因子， n s k和n p k为两个独立分布的高斯噪声。 对于高斯白噪声信道， a s k和a p k都为1。 AWGN (additive white Gaussian noise) 2.纠错的两种方式： ARQ： Automatic Repeat Quest,自动重发请求，前提：检错 FEC：Forward error correct：前向纠错

ARQ:重传反馈（p5) Error Control Automatic Repeat Quest Send several- Send one frames at a frame at a time time Stop and Wait ARQ Slide Windows ARQ Go-back n Selective-reject Data Frame n Waiting time Ack n Data Frame n+ Waiting time ↓ Ack n+1

ARQ：重传反馈（p5) Automatic Repeat Quest Data Frame n Ack n Data Frame n+1 Ack n+1 Waiting time Waiting time Error Control Stop and Wait ARQ Slide Windows ARQ Send one frame at a time Send several frames at a time Go-back n Selective-reject

Stop-and-Wait ARQ:Damaged Frame Sender Receiver Data ACK 1 Data 0 ACK 0 Data 1 Error in NAK Frame 1 Data ACK 1 Flash Time Time

Stop-and-Wait ARQ: Damaged Frame Flash

Stop-and-Wait ARQ:Lost Frame Sender Receiver Data Time out Frame 1 is lost. Data ACK1 Time Time

Stop-and-Wait ARQ: Lost Frame

Stop-and-Wait ARQ:Lost ACK Sender Receiver Data ACK 1 Time out Lost ACK 1 is lost. Data First copy ACK 1 discarded 。 Time Time

Stop-and-Wait ARQ: Lost ACK

SIide Windows Sender window 012345670123456■ Direction Direction This wall moves to the right,frame by frame, This wall moves to the right, when a frame is sent. the size of several frames at a time,when an ACK is received. Receiver window 0I2345670I23456L Direction Direction This wall moves to the This wall moves to the right, right,frame by frame, the size of several frames at when a frame a time,when an is received. ACK is sent

Slide Windows

Sliding Window Example Sender Receiver 0I23456/0I234 0I234560I234- Data 0 02345602Z34e 0I2345时60I23☒4 Data 1 02S34S60234E 0I234560I234F ACK 2 0IZ34时6☑0I☑34 0I234时6☑0I234 Data 2 234560I234 ACK 3 0I23456034 0I234时60234 Data 3 0四Z34时6☑034e 023456023☒4- Data 4 0234的60234 02346☑0234E Data 5 0I2345 ☑0234 0I23456/0IZ34- ACK6 02☑3456☑0234 0U2☑3456☑0234本在

Sliding Window Example