《信道编码即密码》由会员分享,可在线阅读,更多相关《信道编码即密码(8页珍藏版)》请在金锄头文库上搜索。
1、信道编码即密码信道编码即密码信道编码主要知识点正文离散信道模型、离散信道编码设计的目标、离散信道译码准则、离散信道编码设计准则、汉明距离与纠检错能力、近世代数基本概念(群、环、域) 、线性分组码、生成矩阵与监督(校验)矩阵、系统码与非系统码、校验矩阵与纠错能力的关系、汉明码与完备码。循环封闭性、多项式代数、有限域的构造、生成多项式,系统循环码、CRC、循环码的译码、用生成多项式的根定义循环码、BCH 码和 RS码。卷积码基本思路、卷积码的表示形式、概率译码与软判决译码、维特比译码。迭代译码思想与 turbo 码、LDPC 大意。安全编码主要知识点正文信息加密传输的模型、密码攻击、代换、多表代换
2、、置换、DES 与AES、密钥分配与管理。公钥密码体 RSA、公开密钥的认证与签名、利用公钥实现私钥分配。离散信道模型:信道编码:从消息到信道波形或矢量的映射离散信道编码设计的目标:编码的实质:利用冗余降低差错概率离散信道译码准则:最大后验概率准则最大似然准则序列译码准则软输出译码,可供信源信道联合译码:ML 准则和汉明距离译码准则的对应离散信道编码设计准则:准则之一:输出误码率最低简化的设计准则:-针对信道输入输出符号集相同的情况:.检错能力和纠错能力-针对删除信道:.纠删能力检错能力与纠错能力广义的纠错能力,即事实发生错误时,发现其错误的概率,可用错误漏检率来表示-当发生错误的出现概率均匀
3、时,等于消息符号序列数除以编码符号序列数常用的检错能力 e 的定义:检错能力 e:如果在一个码组中发生了热议图案的不多于 e 个比特差错,都能被发现(发生了错误,但不要求发现是什么样的错误) 。纠错能力 t:如果在一个码组中发生了任意软的不多于 t 个比特差错,都能被纠正。最小汉明距离及其与 e 和 t 的关系。两个相同长度的码组之间的汉明距离定义为两个码组对应符号不等的位置的个数。某种给定编码方案的自由距,定义为该编码方案的所有需用码组两两间的汉明距离的最小值。Dmin = dfree = dfdf = e+1,df = 2t + 1,如果在纠 t 个错的同时还要能捡 e 个错,et,则要求
4、 df=e+t+1纠删能力等于最小汉明距离减一(纠删能力是针对删除信道而言的)码的球半径和覆盖半径码空间中以需用码字为中心半径相等的互不相交的球,其最大半径成为码的球半径 s(C)-对自由距为 d 的码,球半径为 s(C) = floor(d-1)/2可以覆盖整个码空间的以许用码字为中心半径相等的球,其最小半径成为码的覆盖半径 t(C),-显然球半径不大于覆盖半径-当相等时成为完备码,在给定 k 和 d 的所有码中 n 最小码长、码距与效率码长:一个编码块编码后的总比特数效率:信息比特数(k)/码长(n)一个分组码,记为(n,k,df)一般而言:-对于给定的码长,效率越低,码距越大-对于给定的
5、效率,码长越长,码距越大。其原因在于编码输出去空间编码,映射的优选成为可能线性码的定义:码字集中的元之间的任一线性组合仍然是合法码子,即对线性组合运算封闭的码子集,称为线性码。群-定义了一种运算的集合-运算封闭(可用加法类比)-有恒等元-有逆元-满足结合律交换群-满足交换律的群环-定义了两种运算的集合-按第一种运算(不妨称为加法)构成交换群-第二种运算(不妨称为乘法)满足一下条件-封闭性 - 结合律 - 与加法间满足分配率域-一种特殊的环-乘法有恒等元(称为 1 元) ,且除了加法的恒等元(称为 0 元)以外都有逆的环-除零元外,对乘法构成交换群无限域,有限域(信道编码中用到的通常是有限域,G
6、F(q))举例:实数域,复数域,二进制域,三进制域子群和陪集。就给定群 G 所定义的(加法)运算封闭的非空子集 H,称 H 为 G 的子群。G 中任一元 g 与 H 相加得到的子集称为 H 的陪集线性空间、线性码与线性分组码。利用线性空间中的子空间作为许用码字的编码称为线性码。当线性空间为有限维空间时即为线性分组码。GF(q)上的 n 维线性空间 Vn 中的一个 K 维子空间 Vn,k 称为(n,k)线性分组码线性分组码的特点、全零序列是许用码字、自由距就是最小码重量线性码的矢量与矩阵表示、 (n,k)线性分组码是 GF(q)上的 n 维线性空间中 k 个线性无关的行向量 c1,c2.ck 张
7、成的、对码空间中任一个码字 C0 可表示为C0 = sigma(i = 1,k)diCi写成行向量形式:C0=d*GG 为生成矩阵监督矩阵(校验矩阵)。若 C 是 n 为线性空间 的一个 k 维子空间,则必存在一个 的n-k 维子空间 H,它与 C 互为零空间。即 CH。 中任一矢量 r 是许用码字的冲要条件是伴随式(校正子)为 0rh1T h2T . Hn-kT=0H = h1;h2;h3;.;hn-k 校验矩阵自由距与校验矩阵。校验矩阵中任意 m 列之间(mdf)互不相关,存在 df 列他们之间是相关的(可用最小码重来证明)。线性分组码的约束使我们可以比较方便的设计编码生成矩阵的特点:、由
8、于 G 的 k 行线性无关,因此至少能找到 k 列线性无关,不妨令这 K 列为前 k 列,即 G= G1,G2,其中 G1 为 k 行 k 列的满秩矩阵、因此有 G = G1Ik,G1-1*G2) = G1Ik Q Q = G1-1*G2、编码时有 c= bG1Ik,Q、如果令 d = bG1 表示信息矢量,则在 c 的前 k 位正好为信息序列的 d、这样的码(即编码序列中直接包含所有信息符号的码)称为系统吗、可见,任何线性分组码都有其等效的系统码形式任意生成矩阵向系统码生成矩阵的转化。即如何找到一组 k 个不相关行向量,刚好也可以作为码空间的一组基。利用行变换,产生 k 个重量为 1 的,相
9、互正交的列。利用列变换,将这 k 列移到最前端。这样就得到了一个前 k 列为单位阵的生成矩阵,用它进行编码得到的输出前 k 个符号正好就是信息序列线性分组码的译码:。即对一个接收到的矢量 r,要根据编码规则判断是否有错,如有可能则纠正其差错。先讨论检错-N 维空间中,许用码组占了 k 维子空间 C-还剩下 r = n - k 维,显然,我们可以找到一个与 C 正交的 r 维子空间 Z-所有的许用码组在 Z 空间中其投影为 0-据此,可以根据 r 在 Z 上的投影是否为 0 来判断是否有错零空间 Z 的基、考虑系统码的生成矩阵 G= Ik Q,其中每一行为码空间的一个基、考察矩阵 H= P Im
10、=-Qt ImGHt = Ik Q-Qt ImT = 0、可见 H 中每一行都与 G 中的每一行正交,因此 H 中这 m 行构成零空间 Z 的所有 m 个基这样就可以根据接受矢量 r 在 H 上的投影 s = rHt(称之为校正子或伴随式)是否为 0 向量来判断 r 是否为许用码组、因此 H 矩阵就被成为校验矩阵校验矩阵的行数、对于一个码长为 n,信息序列长度为 k 的编码,其生成矩阵为 k行 n 列、利用前述方法得到的校验矩阵,有 m=n-k 行-确切的说,校验矩阵的行数至少为 n-k 或者说,校验矩阵的最多有 n-k 行线性无关 校验矩阵的行数最多可以达到 pn-k-1(零空间里的非零向量数)线性分组码的纠错译码。令 r = c+e,e 为误差矢量或错误图案。则校正子为 s = rHT = cHT+eHT = eHT。显然,不同的校正子 s 所对应的错误图案 e 必然不同。当然,可能会有很多中 e 得到相同的 s当然,可能会有很多种 e 得到相同的 s。 如果遍历所有 e,可能会有多少种不同的 s? pn-k 种,零空间里的矢量个数 误差图案总数为有 pn 种,因此得到同一个校正子 s 的误码图案 e 的个数将有 pk 种 事实上,许用码字集合作为一个子群时,它的一个陪集内的所有矢量作为错误图案的校正子都相同 即一个陪集对应一种校正子