网络通信与OSI_3b.ppt

计算机网络与通信 主讲 蔡伟鸿汕头大学工学院计算机系 第三章 数据通信 概论差错控制编码数据通信基础传输控制电路时钟同步技术 第六节差错控制编码 纠错编码的基本原理常用的简单编码线性码循环码原理 数据通信系统模型 1 纠错编码的基本原理 例子 晴 雨 的编码分组码 由信息码分组 附加若干监督码组成 k个信息 r个监督 汉明距离 两个码组对应位上数字不同的位娄称码距 码重 每个码中的 1 个数 最小码距的与检错和纠错能力的关系 为检测E个错码 要求最小码距 d e 1 最小码距的与检错和纠错能力的关系 为纠正t个错码 要求最小码距 d 2t 1 最小码距的与检错和纠错能力的关系 为纠正t个错码 同时检测e个错误 要求条件 t e d t e 1 2 常用的简单编码 奇偶监督码 在偶数监督码中 无论信息位有多少 监督位只一位 它使码组中 1 的数目为偶数 即要求 常用的简单编码 二维奇偶监督码 奇数个错误数字可检测可能检测偶数个错误不能检测的情况有构成矩形的四个错码 常用的简单编码 恒比码 在恒比码中 每个码组含有相同数目的 1 和 0 检测时 只计算接收码组中 1 的数目是否对电传机传输汉字钟 与口取了 的恒比码数字码保护码国际码数字码保护码国际码10101111101610101101012110011100171110011100310110100008011100110041101001010910011000115001110000100110101101 常用的简单编码 恒比码 检错能力 可检所有奇数个码元的错误及部分偶数个码元的错误 但不能检测同时 1 变 0 和 0 变 1 的偶个码元的错误 例子 常用的简单编码 正反码 编码 正反码的监督位数目和信息位数目相同 监督码元信息码元相同或相反 则由信息码中 1 的个数而定 设码长N 10 R 5 K 511001 1100111001 奇数 1 10001 1000101110 偶数 1 常用的简单编码 正反码 解码 信息位和监督位按位模2相加 得一合成的码组 若信息位有奇个 1 为检验码组 若信息位有偶个 则取反码为校验码组 校验规则如下 1 全为 0 元错码2 有4个 1 1个 0 信息码中有一位错码 与 0 位置3 有4个 0 1个 1 4 其它错码多于1个 常用的简单编码 交织码 在原有检错能力条件下 解决连续错误 3 线性码 各种编码依据的原理不同奇偶监督码的编码原理利用了代数关系式代数码 建立在代数学基础上的编码 其中有线性码 线性码中信息位和监督位是由一些线性代数方程构成的 汉明码 偶数监督码的构成 S S只有两种情况0 无错1 有错若把监督位设为两位 有四种情况 00 无错 01 10 11表示1位错码的3种不同位置 同理R 位监督可指示一位错位的 22 1 个不同位置 汉明码 构造一种能纠正一位错码的编码 设码长为n 信息位数为k 则监督位数r n k 要r位监督位数能指示一位错码的几种可能位置 则要求 2r n或2r k r 举例 k r 即n 码 汉明码 构造一种能纠正一位错码的编码 用a6a5a4a3a2a1a0表示这 个码元 用 表示三个监督关系式的校正子 错码位置 错码位置 a0 a4 a1 a5 a2 a6 a3 无错 汉明码 构造一种能纠正一位错码的编码 a a a a a a a a a a3 a a 当无错时 a a a a a a a a a a3 a a 汉明码 构造一种能纠正一位错码的编码 a0 a3 a4 a a1 a3 a5 a 监督位的生成式a2 a4 a5 a 信息码 可得码 a3 错位 线性码 1 A6 1 A5 1 A4 0 A3 1 A2 0 A1 0 A0 01 A6 1 A5 0 A4 1 A3 0 A2 1 A1 0 A0 01 A6 0 A5 1 A4 1 A3 0 A2 0 A1 1 A0 0HAT0 A6 1110100 A5 0 1101010 A4 0 1011001 A3 0 A2 A1 A0 线性码 记为H AT 0T或A HT 0其中H称为监督矩阵 A为一码组 1110100 1110100 H 1101010 1101010 PIr 1011001 1011001 H矩阵的各行是线性无关 即秩为R 线性码 由生成式可得 A2 1110 A6 A1 1101 A5 A0 1011 A4 A3 A2A1A0 A6A5A4A3 111 A6A5A4A3 Q 110 101 011 Q PT 线性码 1000111 令G IQ 0100110 0010101 0001011 称G为生成矩阵 G或A GG的各行是线性关系的 由G可构成个码组 推广到一般 N元码组 A 线性码 设B为接收码组 B A E为错码行矩阵E B A H BH AH BH EH S若B A 则 B A H 0若BA 则S BHSi EiS1 Sn E1 EnSijS为校正子 利用它来指示错码位置 线性码的封闭性 线性码中的任意两个码字之和仍为这种码中的一个码字 证明 4 循环码原理 循环码的性质及特点1 循环码除线性码的一般性质外 还具有循环性2 循环码的编码和解码设备不太复杂 且检 纠 错的能力较强 若xn 1 xn 2 x2 x 1是一个循环码字 则xn 2 xn 3 x 1 xn 1xn 3 xn 4 1 xn 1 xn 2也是在该编码中的码字 循环码原理 例 7 3 循环码11001011001011001011101011101011100011100111100100000000用一多项式来表示 xn 1 xn 2 x2 x 1 为体现循环性及数学表达式 T x xn 1 xn 2 x2 x 1第1码组可表示为T1 x x6 x5 x2 1 循环码原理 在整数运算中 M N Q P NP N则按模N运算下 有M Q N PP 模N 类似 对任一多项式F x 被一N次多项式N x 除 得到商式Q x 和一个次数小于N的余式R x 即F X N X Q X R X 则有F X R X 模N X 循环码原理 如x3被 x3 1 除 有x3 x3 1 1 1 模x3 1 同理x4 x2 1 x2 x 1 模x3 1 练习 x5 x3 x性质 在循环码中 若xiT X 是一个长为N的许用码字 则T X 在按模xn 1运算下 亦是一个许用码字 即若xiT X T X 模 1 则T X 也是一个许用码字 证明 循环码原理 11001011001011001011101011101011100011100111100100000000例T1 x x6 x5 x2 1左循环移位3次T x x3 x6 x5 x2 1 x5 x3 x2 x1 模xn 1 n 7 0101110 练习 T2 x x4 x2 x 1 循环码原理 构成生成矩阵GG为K行N列 G中每一行都为一码组 且线性无关 则若能找到K个已知码组 就能构成矩阵后 用g X R次方 生成多项式 表示 N K 码中前 K 1 位皆为 0 的码组 即若有第一位信息位为 1 则g X xg X Xk 1g x 都是码组 且这K个码组是线性关系的 可构成G g X 的唯一性及存在性 讨论 循环码原理 a6 a5 a4 a3 a2 a1 a0 a6 a5 a4 a3 G或A a6 a5 a4 a3 G g x xg X G x Xk 2g x Xk 1g x T X H x g x 结论 循环码原理 编 解码方法 设 N K 码 生成多项式为G X M X 为信息码多项式 次数小于K 则T X Xn km x r x 勘误 r x 为Xn km x g x 的余式 证明 举例 g x x4 x2 x 1m x x2 1 举例 练习 7 4 例子 10 6 例子 标准CRC生成多项式G x CRC 12G x x12 x11 x3 x2 x 1CRC 16G x x16 x15 x2 1CRC CCITTG x x16 x12 x5 1CRC 32G x x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x 1 第七节 数据通信基础 一 二进制串行传输在设备体内 一般采用并行传输在设备间 一般采用串行传输二 通信的模式演讲 讲话 单向传输信息对话 双向传输信息1单工数据只在一个方向上传输的模式2半双工两台设备能交替交换数据的模式3全双工两台设备能同时交换数据的模式 第七节 通信基础 三 传输模式传输中为正确确认每一个比特数据必须知道 1 比特速率 2 每一元素的启始 3 每一元素的末端时钟同步字符同步帧同步通信可分为异步传输同步传输 三 传输模式 1异步传输当被传输数据的时间间隔是随机时 通常采用异步传输每一符号的起始比特 1 0 每一符号的终止比特1为了可靠接收 时钟必须高于传输BIT率的N倍 每一传输单元包含10个比特1个起始 8个字符 1个结束波特率 BAND 的定义 每秒种传输信号的数量 当传输二进制信号时 1BPS 1BAND当传输多进制信号时 1BPS 1BAND 三 传输模式 1异步传输当被传输数据的时间间隔是随机时 通常采用异步传输每一符号的起始比特 1 0 每一符号的终止比特1为了可靠接收 时钟必须高于传输BIT率的N倍 每一传输单元包含10个比特1个起始 8个字符 1个结束波特率 BAND 的定义 每秒种传输信号的数量 当传输二进制信号