线性分组编码
线性分组编码
内容提要 线性分组码概述 校正子 n最小距离 检测和纠错能力 标准阵 BSC上的漏检误码率 SPC,重复码,对偶码
内容提要 ◼ 线性分组码概述 ◼ 校正子 ◼ 最小距离 ◼ 检测和纠错能力 ◼ 标准阵 ◼ BSC上的漏检误码率 ◼ SPC，重复码，对偶码
线性分组码概述 假设信源输出的信息比特是一串二进制0和1 分组码将其分割为固定长度为的消息分组( message block 每个分组记作u,故共有2k个不同的消息分组 ■编码规则按照一定的规则将输入映射为二进制n维向 量ν,n>k,ν是u的码字或码向量,有2k种不同的码字, 这些码字的集合叫做一个分组码 y和u之间是一一对应的 ■当n和很大时,编码器要存储这种对应关系代价很高, 除非这种对应关系有规律利用(线性?)
线性分组码概述 ◼ 假设信源输出的信息比特是一串二进制0和1 ◼ 分组码将其分割为固定长度为k的消息分组（message block） ◼ 每个分组记作u，故共有2 k个不同的消息分组 ◼ 编码规则按照一定的规则将输入u映射为二进制n维向 量v，n>k，v是u的码字或码向量，有2 k种不同的码字， 这些码字的集合叫做一个分组码 ◼ v和u之间是一一对应的 ◼ 当n和k很大时，编码器要存储这种对应关系代价很高， 除非这种对应关系有规律利用（线性？）
线性分组码, linear block codes 定义:(n,k)分组码,当且仅当其全部码字构 成域GF(2)上所有n维向量组成的向量空间的 个维子空间时被称为(n)线性码 个二进制分组码是线性的充要条件是任意两 个码字的模2和仍是该分组码中的一个码字 (模2和运算封闭) 一个(n,线性码C是所有二进制n为向量构成的 向量空间V的一个k维子空间,故可在V中找 到k个独立的码字g18281做为基,用来表 示C中任意一个码字P=图+图, …+uk-18k-1 式中,u2=0或1,0≤i<k
线性分组码，linear block codes ◼ 定义：（n,k）分组码，当且仅当其全部码字构 成域GF(2)上所有n维向量组成的向量空间的一 个k维子空间时被称为 (n,k)线性码 ◼ 一个二进制分组码是线性的充要条件是任意两 个码字的模2和仍是该分组码中的一个码字 （模2和运算封闭） ◼ 一个(n,k)线性码C是所有二进制n为向量构成的 向量空间Vn的一个k维子空间，故可在Vn中找 到k个独立的码字g1 ,g2 ,…,gk-1做为基，用来表 示C中任意一个码字
线性分组码 G的行生成或张成(span)线性码C, 故G称为生成矩阵。线性分组码C的任 何k个基都可以获得一个生成矩阵G,故 编码器只需要存储一组基就可以依据输 入的信息序列得到码字 用这k个基为间量7用大Rn g go 0.n-1 g g G g g10 11 g12 1,n-1 8 gk-1.0Bk-1,1吕k-1,2 g k-1,A-1 设=(to,04…,"k-1)是带编码的信息序列,则 对应的码字为: 80 81 V=l,G=(l0,u1, 080+u11+…+lk-1gk-1 8k-1
线性分组码 ◼ 用这k个基为行向量构成矩阵Gkxn ◼ (1) ◼ 设 是带编码的信息序列，则 对应的码字为： G的行生成或张成（span）线性码C， 故G称为生成矩阵。线性分组码C的任 何k个基都可以获得一个生成矩阵G，故 编码器只需要存储一组基就可以依据输 入的信息序列得到码字
7,4线性分组码例子 01000 G gggg 0123 10100 10010 10 000 l=(1101)是带编码的信息序列,其对应码字 为:=1·g+1·g;+0·g2+1·g =(1101000)+(0I10100)+(1010001) =(0001101)
(7,4)线性分组码例子 ◼ u=(1 1 0 1)是带编码的信息序列，其对应码字 为：
具有系统结构的线性分组码 下图显示分组码的系统结构,包括冗余校验部 分和消息部分 消息部分包括k个未经改变的原始消息 冗余校验部分包括n-个奇偶校验位,这些位 是信息位的线性和 称为线性系统分组码 冗余校验部分 消息部分 n植位一—k位
具有系统结构的线性分组码 ◼ 下图显示分组码的系统结构，包括冗余校验部 分和消息部分 ◼ 消息部分包括k个未经改变的原始消息 ◼ 冗余校验部分包括n-k个奇偶校验位，这些位 是信息位的线性和 ◼ 称为线性系统分组码
线性系统分组码 矩阵 k×k单位阵 g Pot 100 0 10 P1 11 1,n~k-1 010 0 G g (2) P n-k-1 001 0 8k k-1,0 Pk k-1, P 码字v的左边就是 待编码信息序列分组码可由上述km的矩阵 码字ν的右边就是待编 的线性和x则有G= 码信息序列u TT下 Pl],则=( 为 Vn-1=(uo, ur G,y的分量: n-k+ 1K0≤i<k =WPo+uPn+…+lk-1/Pk-1,for0≤j<n-k
线性系统分组码 (2) ◼ 一个线性系统分组码可由上述kxn的矩阵G来描述，若记k 阶单位阵为Ik，则有G=[P Ik ]，则 的码字 为： ，v的分量： 码字v的右边就是待编 码信息序列u 码字v的左边就是 待编码信息序列u 的线性和
奇偶校验矩阵 ■对任何由k个线性独立的行向量组成的kn矩阵G,都 存在一个有n-个线性独立的行向量组成的(n-k)xm矩阵 H,使得G的行空间的任意向量与H的行向量正交,且 任何与H正交的向量都在G的行空间内。故: 口一个n维向量v是G生成的码C中的一个码字,当且仅当 ,H=0 口码C称为H的零空间,H称为码的奇偶校验矩阵 口矩阵H的行向量有2n中组合方式,构成(m,n-k)线性码C动,这 个码是G的零空间 是C的对偶码, dual code 口一个线性码的奇偶校验矩阵是其对偶码的生成矩阵
奇偶校验矩阵 ◼ 对任何由k个线性独立的行向量组成的kxn矩阵G，都 存在一个有n-k个线性独立的行向量组成的(n-k)xn矩阵 H，使得G的行空间的任意向量与H的行向量正交，且 任何与H正交的向量都在G的行空间内。故： ❑ 一个n维向量v是G生成的码C中的一个码字，当且仅当 ❑ 码C称为H的零空间，H称为码的奇偶校验矩阵 ❑ 矩阵H的行向量有2 n-k中组合方式，构成(n,n-k)线性码Cd，这 个码是G的零空间 ❑ Cd是C的对偶码，dual code ❑ 一个线性码的奇偶校验矩阵是其对偶码的生成矩阵
奇偶校验矩阵 若(n.)线性码的生成矩阵公式(2)所示,则其奇 偶校验矩阵为公式(3) 100…0poo P P P [L,P]=001 0 P P12 1,2 000 Po,n-k- PI -4-1 P k-1,n=k-1 令h表示H的任意一行向量,可以证明公式(2) 中的行向量g与h的内积为0,即 g/*h;=Pi+P=0也就是G.H=0
奇偶校验矩阵 ◼ 若(n,k)线性码的生成矩阵公式(2)所示，则其奇 偶校验矩阵为公式(3) (3) ◼ 令hi表示H的任意一行向量，可以证明公式(2) 中的行向量gj与hi的内积为0，即 也就是