[分享]信道编码即密码
信道编码即密码
信道编码主要知识点
正文
离散信道模型、离散信道编码设计的目标、离散信道译码准则、离散信道编码设计准则、汉明距离与纠检错能力、近世代数基本概念(群、环、域)、线性分组码、生成矩阵与监督(校验)矩阵、系统码与非系统码、校验矩阵与纠错能力的关系、汉明码与完备码。循环封闭性、多项式代数、有限域的构造、生成多项式,系统循环码、CRC、循环码的译码、用生成多项式的根定义循环码、BCH码和RS码。卷积码基本思路、卷积码的表示形式、概率译码与软判决译码、维特比译码。迭代译码思想与turbo码、LDPC大意。
安全编码主要知识点
正文
信息加密传输的模型、密码攻击、代换、多表代换、置换、DES与AES、密钥分配与管理。
公钥密码体RSA、公开密钥的认证与签名、利用公钥实现私钥分配。
离散信道模型:
信道编码:从消息到信道波形或矢量的映射
离散信道编码设计的目标:
编码的实质:利用冗余降低差错概率
离散信道译码准则:
最大后验概率准则
最大似然准则
序列译码准则
软输出译码,可供信源信道联合译码:
ML准则和汉明距离译码准则的对应
离散信道编码设计准则:
准则之一:输出误码率最低
简化的设计准则:
--针对信道输入输出符号集相同的情况: .检错能力和纠错能力
--针对删除信道:
.纠删能力
检错能力与纠错能力
广义的纠错能力,即事实发生错误时,发现其错误的概率,可用错误漏检率来表示
--当发生错误的出现概率均匀时,等于消息符号序列数除以编码符号序列数
常用的检错能力e的定义:检错能力e:如果在一个码组中发生了热议图案的不多于e个比特
差错,都能被发现(发生了错误,但不要求发现是什么样的错误)。
纠错能力t:如果在一个码组中发生了任意软的不多于t个比特差错,都能被纠正。
最小汉明距离及其与e和t的关系
。两个相同长度的码组之间的汉明距离定义为两个码组对应符号不等的位置的个数
。某种给定编码方案的自由距,定义为该编码方案的所有需用码组两两间的汉明距
离的最小值。Dmin = dfree = df
df >= e+1,
df >= 2t + 1,
如果在纠t个错的同时还要能捡e个错, e>t,则要求df>=e+t+1
纠删能力等于最小汉明距离减一(纠删能力是针对删除信道而言的)
码的球半径和覆盖半径
码空间中以需用码字为中心半径相等的互不相交的球,其最大半径成为码的球半径s(C)
--对自由距为d的码,球半径为s(C) = floor[(d-1)/2]
可以覆盖整个码空间的以许用码字为中心半径相等的球,其最小半径成为码的覆盖半径t(C),
--显然球半径不大于覆盖半径
--当相等时成为完备码,在给定k和d的所有码中n最小
码长、码距与效率
码长:一个编码块编码后的总比特数
效率:信息比特数(k)/码长(n)
一个分组码,记为(n,k,df)
一般而言:
--对于给定的码长,效率越低,码距越大 --对于给定的效率,码长越长,码距越大 。其原因在于编码输出去空间编码,映射的优选成为可能
线性码的定义:
码字集中的元之间的任一线性组合仍然是合法码子,即对线性组合运算封闭的码子集,称为线性码。
群--定义了一种运算的集合
--运算封闭(可用加法类比)
--有恒等元
--有逆元
--满足结合律
交换群
--满足交换律的群
环--定义了两种运算的集合
--按第一种运算(不妨称为加法)构成交换群 --第二种运算(不妨称为乘法)满足一下条件 --封闭性 -- 结合律 -- 与加法间满足分配率
域--一种特殊的环
--乘法有恒等元(称为1元),且除了加法的恒等元(称为0元)以外都有逆的环
--除零元外,对乘法构成交换群
无限域,有限域(信道编码中用到的通常是有限域,GF(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张成的
、对码空间中任一个码字C0可表示为 C0 = sigma(i = 1,k)diCi
写成行向量形式:C0=d*G
G为生成矩阵
监督矩阵(校验矩阵)
。若C是n为线性空间Ω的一个k维子空间,则必存在一个Ω的n-k维子空间H,它与C互为零空间。即C?H 。Ω中任一矢量r是许用码字的冲要条件是伴随式(校正子)为0
r[h1T h2T .... Hn-kT]=0
H = [h1;h2;h3;....;hn-k] 校验矩阵
自由距与校验矩阵
。校验矩阵中任意m列之间(m
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
得到的校验矩阵,有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种
– 事实上,许用码字集合作为一个子群时,它的一个陪集内的
所有矢量作为错误图案的校正子都相同 – 即一个陪集对应一种校正子