信息论与编码理论基础(第六章)

第六章：线性分组码§6.1 分组码的概念(与主教材标题不同) §6.2 线性分组码 §6.3 线性分组码的校验矩阵(与主教材标 题不同) §6.5 译码方法和纠错能力(与主教材标题 不同) §6.4 、§6.6、§6.7、§6.8 一些特殊 的线性分组码2016/1/9 1

§6.1 分组码的概念设信道是一个D元字母输入/ D元字母输出的DMC信道，字母 表为{0, 1, …, D-1}。其信道转移概率矩阵为D×D矩阵 1 p p D 1 p D 1 p D 1 p 1 p D 1 p 1 p D 1 p D 1

传输错误的概率为 p。信道容量为 C=logD-H(p)-plog(D-1)。2016/1/9 2

§6.1 分组码的概念对随机变量序列X1X2…进行的信道编码为(N, L)码： (X1X2…XL)→(U1U2…UN)=C(X1X2…XL)。 这个(N, L)码又称为(N, L)分组码。 已经有结论：当设备所确定的编码速率R<C/H(X)时， 存在 (N, L)分组码，使得 实际编码速率 (信息率L/N)任意接近R, 译码错误的概率任意接近0。 问题是：怎样构造这样的分组码？这样的分组码的编码、译 码计算量会不会太大？(这才是研究分组码的含义)2016/1/9 3

§6.1 分组码的概念预备知识1:有限域 设D是一个素数。于是字母表{0, 1, …, D-1}中的所有字母关 于(modD)加法、(modD)乘法构成了一个封闭的代数结构， 称作有限域，又称作Galois域，记作GF(D): GF(D)=({0, 1, …, D-1}, (modD)加法, (modD)乘法)。 即 (1)({0, 1, …, D-1}, (modD)加法) 构成交换群(Abel群)。 (2)({1, …, D-1}, (modD)乘法) 构成交换群(Abel群)。 (3)分配律成立：a(b+c) (modD) =ab+ac(modD)。2016/1/9 4

§6.1 分组码的概念注1:如果D不是素数， ({0, 1, …, D-1}, (modD)加法, (modD)乘 法)不是有限域，只是有限环。 注2:有限域GF(D)上的线性代数完全类似于实数域上的线性代 数，线性代数的所有内容都在“加法”和“乘法”基础上得 到。 元素的“加法”负元；非0元的“乘法”逆元； 一组向量是否“线性无关”的概念以及所有等价的判别方法； 矩阵的“秩”的概念以及所有计算方法； 方阵是否“可逆”的所有判别方法； 求方阵的“逆阵”的所有算法； 关于对称矩阵的所有结论；等等。 注3:有限域GF(D)与实数域的区别是：传统的“逼近”、“极 限”的概念消失了。2016/1/9 5

例：取D=2,则GF(2)=({0, 1}, (mod2)加法, (mod2)乘法)。 运算规则为： 0+0=1+1=0,0+1=1, 0×0=0×1=0,1×1=1。1 0 1 方阵 1 1 0 是否可逆？回答是肯定的。两种不同的判 0 1 0

别方法都能够证明它是可逆的 ： (1)它经过可逆行变换能够变成单位阵； (2)它的行列式不等于0。(等于1!)1 1 02016/1/9

0 1 1

1 0 0 1 0 0 0 0 1

0 06

§6.1 分组码的概念该方阵的逆矩阵是什么？ 怎样计算？做联合可逆行变换： 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1

1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 02016/1/9

0 1 1

1 0 0

1

0 0 1

1 1 0 1 1 1 7

§6.1 分组码的概念例：取D=3,则GF(3)=({0, 1, 2}, (mod3)加法, (mod3)乘法))。 运算规则为：0+0=1+2=0,0+1=2+2=1,0+2=1+1=2, 0×0=0×1==0×2=0,1×1=2×2=1,1×2=2。矩阵 1 2 0 1 1 1 0 1 1 1 0 0

是不是满行秩的？

换句话说，此矩阵的三个行向量是不是在域GF(3)上线性无关 的？再换句话说，能否保证此矩阵的各行的任何非0线性组 合都不是全0的4维向量？再换句话说，此矩阵能否通过一 些可逆行变换变成一个“阶梯阵”?2016/1/9 8

§6.1 分组码的概念可逆行变换 1 1 0 1 1 1 0 1 1 1 0 1 2 1 1 0 0 2 1 1 0 2 1 1 0 1 1 0 0 1 1 0 0 0 2 1

1 2 0

1 1 1

0 1 1

1 0 是满行秩的。 0

2016/1/9

§6.1 分组码的概念例：域GF(D)上的一个L行N列的矩阵(L×N阶的矩阵)G, 设它是满行秩的(当然此时有L≤N)。则变换 (u1, u2, …, uN)=(x1, x2, …, xL)G 一定是单射(即(x1, x2, …, xL)的不同值一定变换为(u1, u2, …, uN) 的不同值)。 证明 设u(1)=x(1)G, u(2)=x(2)G ,且x(1)≠x(2)。要证明u(1)≠u(2)。 根据线性性质， u(1)-u(2)=(x(1)-x(2))G, 因为(x(1)-x(2))≠全0的L维向量，所以(x(1)-x(2))G是G的各行的非0 线性组合。G满行秩，所以(x(1)-x(2))G≠全0的N维向量。所 以u(1)≠u(2)。2016/1/9 10

§6.1 分组码的概念预备知识2:有限域上的分组码 当D是素数时，分组码可以充分利用有限域GF(D)的 代数运算，使得编码和译码更加简便。

2016/1/9

§6.2 线性分组码定义 取GF(D)上的一个L行N列的矩阵G,它是满行秩的。 (N, L)分组码定义为 (u1, u2, …, uN)=(x1, x2, …, xL)G 其中(x1, x2, …, xL)是信息向量，(u1, u2, …, uN)是对应的码字。 (1)称此码为D元(N, L)线性分组码。 (2)称矩阵G为此码的生成矩阵。

2016/1/9

§6.2 线性分组码线性分组码的代数结构 命题1 不同的信息向量对应不同的码字。 (因为矩阵G是满行秩的，所以变换u=xG是单射) 命题2 生成矩阵G的第1行是信息向量(1, 0, 0, …, 0)的码字； 生成矩阵G的第2行是信息向量(0, 1, 0, …, 0)的码字； … 生成矩阵G的第L

行是信息向量(0, …, 0, 0, 1)的码字。

2016/1/9

§6.2 线性分组码命题3 信息向量(x1, x2, …, xL)的码字是： x1数乘G的第1行，加x2数乘G的第2行，加…,加xL数乘G的第L 行。 换句话 …… 此处隐藏：1604字，全部文档内容请下载后查看。喜欢就下载吧 ……