当前位置：文档之家 › 信息论课程设计之线性分组码的计算

信息论课程设计之线性分组码的计算

  • 格式：docx
  • 大小：27.50 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

信息论与编码_第7章线性分组码

信息论与编码_第7章线性分组码
信息论与编码
Information and Coding Theory
第7章 线性分组码
王永容 机械与电气工程学院 wangyr416@
1
线性分组码
线性分组码概念 线性分组码的生成矩阵 线性分组码的校验矩阵 线性分组码的最小汉明重量 线性分组码的译码 完备码 汉明码
2
线性分组码概念 (n, k)线性分组码=“(n, k)分组”+“线性” 2元 (n, k)分组码 f : S=(F2)k C (F2)n m=(m2,…,mk)c=(c1c2,…,cn) C是(F2)n的一个k维线性子空间！
系统生成矩阵 1 0 0 1 1 1 Gs 0 1 0 1 1 0 I | P 0 0 1 0 1 1
校验矩阵 1 1 0 1 0 0 H P T | I 1 1 1 0 1 0 . 1 0 1 0 0 1
1 1 1 0 1 1 [000]. 0 0 1 0 0 1
17
线性分组码的校验矩阵
例7-2（续2）：求对偶码C
1 1 0 1 0 0 对偶码的生成矩阵=校验矩阵H 1 1 1 0 1 0 . 1 0 1 0 0 1
c mH , c1 m1 m2 m3 c m m 1 2 2 c3 m2 m3 c4 m1 c5 m2 c6 m3
f
F2n S=F2k
C
4
线性分组码
线性分组码概念 线性分组码的生成矩阵 线性分组码的校验矩阵 线性分组码的最小汉明重量 线性分组码的译码 完备码 汉明码
5
线性分组码的生成矩阵
生成矩阵 C是F2n的一个k维线性子空间，设{g1,g2,…, gk}是C的一个基

信息论与编码第6

信息论与编码第6

第6章 线性分组码
6.1.2 码的重量和码的距离 在信道编码中，定义码字中非零码元的数目为码字的汉
明（Hamming)重量，简称码重。例如“010”码字的码重为 1，“011”码字的码重为2。把两个码字之间对应码位上具 有不同二元码元的位数定义为两码字的汉明距离，简称码距。 在一种编码中，任意两个许用码字间距离的最小值，即码字 集合中任意两码字间的最小距离，称为这一编码的最小汉明 距离，以dmin表示；在非零码字中，重量最小者称为该码的 最小汉明重量。
已知(n，k，d)线性分组码的最小距离dmin≤n－k＋1。若 系统码的最小距离dmin＝n－k＋1，则称此码为极大最小距离 可分码，简称MDS码。
第6章 线性分组码
6.1.3 码的检错及纠错能力
下面讨论码的检错、纠错能力与最小码距的数量关系。
在一般情况下，对于分组码有以下结论：
(1)若一个码组内能检测e
第6章 线性分组码
【例6－2】 已知GF(2)中码组C= ｛0000,1010,0101,1111｝是一个分组长度n=4的线性分组码。 观察码字之间所有十种可能的和：
0000+0000=0000,0000+1010=1010,0000+0101=0101, 0000+1111=1111,1010+1010=0000,1010+0101=1111, 1010+1111=0101,0101+0101=0000,0101+1111=1010, 1111+1111=0000 它们都在C中，全零码字也在C中。该码组的最小距离为 dmin=2。为了验证这个线性码的最小距离，可计算所有码字 对（共6对）之间的距离:
第6章 线性分组码

信息论与编码 8 线性分组码

信息论与编码 8 线性分组码

。所以非空集合{0,1}是两种运算法则 和
GF(2):{0,1}
8.plus 线性分组码的代数结构
5 线性空间及子空间
（一）线性空间
设GF是一个数域，N是任一类运算对象的非空集合，如在“+”和“∙”
两种运算法则下，满足下列条件： （1）非空集合N是“+”运算法则的一个交换群； （2）非空集合N对另外一种运算符“∙”，满足封闭性； 设有c ϵGF，V ϵN，则有 (c∙V) ϵN （3）非空集合N对两种法则“+”和“∙”，满足分配率 设c1,c2 ϵGF, V1,V2 ϵN，则有 c1∙(V1+V2) = (c1∙V1) + (c1∙V2)
(c1+ c2)*V1 = (c1∙V1) + (c2∙V1)
则称非空集合N为GF上的线性空间。
把信息序列按一定长度分成若干信息码组, 每组由 k 位
组成;
编码器按照预定的线性规则（可由线性方程组规定），
把信息码组变换成 n 重（n>k）码字，其中 (n－k) 个附 加码元是由信息码元的线性运算产生的。 (2) 线性分组码的码字数：信息码组长 k 位，有 2k 个不同 的信息码组，有 2k 个码字与它们一一对应。
g1-1* g2 ϵH 令g1 =3，g2 =9，则g1-1* g2 ϵH
定理8.9（正交性）：设H是群G的子群，H的两个不同的陪集一定不相交。
如gi*H和gj*H是H的两个不同的陪集，则这两个陪集中没有共同的元素；否 则gi*H和gj*H 是相同的陪集。
令g1 =3，g2 =9， g1的陪集g1*H为{3,5,7,9,1}， g2 的陪集g2*H为{9,1,3,5,7}，是
同一陪集。

第八章线性分组码

第八章线性分组码

第八章线性分组码8.1 什么是检错码？什么是纠错码？两者有什么不同？答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。

8.2 试述分组码的概念，并说明分组码的码率r的意义。

答：分组码是把信息序列以每k个码元分组，即每k个码元组成一个信息组。

n表示码长,k 表示信息位的数目，码率r=k/n，它说明在一个码字中信息为所占的比重。

8.3 什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？答：线性分组码的2个码字将组成n维向量空间的一个k维子空间，而线性空间可由其基底张成，因此线性分组码的个码字完全可由k个独立的向量组成的基底张成。

设k个向量为（7.3-2）将它们写成矩阵形式：（7.3-3）（n,k）码中的任何码字，均可由这组基底的线性组合生成。

即C=MG=(mk-1,mk-2,m0)G式中M=(mk-1,mk-2,m0)是k个信息元组成的信息组。

这就是说，每给定一个信息组，通过式（7.3-3）便可求得其相应的码字。

故称这个由k 个线性无关矢量组成的基底所构成的k×n阶矩阵G为码的生成矩阵（Generator Matrix）。

校验矩阵H 的每一行代表求某一个校验位的线性方程的系数(n-k)线性分组码有r=n-k 个校验元，故须有r 个独立的线性方程，因此H 矩阵必由线性无关的r 行组成，是一个(n-k)×n 阶矩阵，一般形式为一个（n,k ）线性分组码生成矩阵有k 行n 列校验矩阵有(n-k)行n 列。

8.4 什么样的码成为系统码？系统码的生成矩阵和校验矩阵在形式上有何特点？答：若信息组为不变的形式，称在码字的任意k 位中出现的码为系统码；一个系统码的生成矩阵G ，其左边k 行k 列是一个k 阶单位方阵，系统码的校验矩阵H ，其右边r 行r 列组成一个r 阶单位方阵。

8.5 什么是对偶码？试举例说明之。

线性分组码

线性分组码

C mG
G是一个k*n阶矩阵，称为(n,k)码的生成矩阵。
7
1 0 G 0
0 0 1 0 0 1
p11 p 21 p k1
p12 p 22 pk 2
p1( n k ) p 2( nk ) I P k pk ( nk )
n 1
u和v之间的距离表示2个码字对应位不同的数目。
如(7,3)码的两个码字：u=0011101
v=0100111
它们之间的距离d=4
4
码的最小距离的dmin ：在（n,k）线性码字集合中， 任意两个码字间的距离最小值，是衡量抗干扰能力的 重要参数，dmin越大，抗干扰能力越强。 码字的重量W：码字中非零码元符号的个数；在二元 线性码中，码字的重量是码字中含“1”的个数。 码的最小重量Wmin：线性分组码中，非零码字重量的 最小值，称为码的最小重量，表示为：
限， 性能界限，即码的译码错误概率的上、下 限。 对码距限而言，最重要的限是汉明限，普 洛特金限和吉尔伯特－瓦尔沙莫夫限，汉 明码和普洛特金限告诉我们，在给定码长n 和码的传输速率R=k/n下，最小距离可以达 到的最大值，故它们都是上限，而吉尔伯 特一瓦尔沙莫夫限给出了码的最小距离的 下限。
HC 0
T
T
r=n-k
H
阵是n列，(n-k)行的矩阵；
为了得到确定的码，r个监督方程必须是线性
无关的，即要求H阵的秩为r。
6
2. 生成矩阵G
把方程组写成矩阵的形式为
h11 h 21 h r1
h12 h1k h 22 h 2k h r2 h rk
m 信道编码
C

信息论第九讲-代数基础与线性分组码

信息论第九讲-代数基础与线性分组码
表示所有G中的元素。 例：设G是整数集合，在普通加法+下为一个交 换群，而H为G的一个子群，它由整数m的倍数 构成，那么，所有正整数均可用H中的元素表示 ，且划分为子群H的若干个陪集。 H:{nm}; n=0,±1,±2,…。 例如m=3,则子群H的元素为： H:{0, ±3, ±6, ±9, ±12, ±15, ±18,…} 利用分元陪集的方法，用H的元素表示G中的所 有元素。
•GF(2)上的多项式若有偶数项，则一定可被x+1除 尽。
•对于任意m≥1,都存在m次不可约多项式。
•GF(2) 上 的 任 意 m 次 不 可 约 多 项 式 ， 一 定 能 除 尽
xn+1，其中n=2m-1。
例如：x3+x+1,可以除尽x7+1。
2019/11/24
16
x3+x+1
2019/11/24
• 这样，利用分元陪集的方法，可以构成所有G中 的元素。
陪集1
0
3
-3
6
-6
9
-9
…
陪集2
1+0= 1
1+3= 4
-2
7
-5
10
-8
…
陪集3
2+0= 2
2+3= 5
-1
8
-4
11
-7
…
2019/11/24
6
5.4.2 域(Field)
[域的定义]：如果一个元素集合F，在其中定义加法 和乘法两种运算，并满足下列条件则称为一个域
2019/11/24
2
例如：p=5为一个素数, G={1,2,3,4}为一个乘法 群，
*
1

线性分组码(免费)

线性分组码8.3.1 基本概念是一组固定长度的码组，可表示为（n, k），通常它用于前向纠错。

在分组码中，监督位被加到信息位之后，形成新的码。

在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。

当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为。

对于长度为n的二进制线性分组码，它有种可能的码组，从种码组中，可以选择M=个码组（k<n）组成一种码。

这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。

线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的如下：（1）任意两许用码之和（对于二进制码这个和的含义是模二和）仍为一许用码，也就是说，线性分组码具有封闭性；（2）码组间的最小码距等于非零码的最小码重。

在8.2.1节中介绍的奇偶监督码，就是一种最简单的线性分组码，由于只有一位监督位通常可以表示为（n,n-1），式（8-5）表示采用偶校验时的监督关系。

在接收端解码时，实际上就是在计算：（8-6）其中，…表示接收到的信息位，表示接收到的监督位，若S＝0，就认为无错；若S＝1就认为有错。

式（8-6）被称为监督关系式，S是校正子。

由于校正子S的取值只有“0”和“1”两种状态，因此，它只能表示有错和无错这两种信息，而不能指出错码的位置。

设想如果监督位增加一位，即变成两位，则能增加一个类似于式（8-6）的监督关系式，计算出两个校正子和，而共有4种组合：00，01，10，11，可以表示4种不同的信息。

除了用00表示无错以外，其余3种状态就可用于指示3种不同的误码图样。

同理，由r个监督方程式计算得到的校正子有r位，可以用来指示-1种误码图样。

对于一位误码来说，就可以指示-1个误码位置。

对于码组长度为n、信息码元为k位、监督码元为r＝n - k位的分组码（常记作（n，k）码），如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能，则要求：（8-7) 下面通过一个例子来说明的。

8.2 线性分组码 线性分组码编码

第八章 差错控制编码
8.2 线性分组码
线性分组码的编码
1
引言
• 信道编码，目的是提高数字通信的可靠性
– 差错率是信噪比的函数
• 信道编码，差错控制编码，抗干扰编码
• 信道编码过程：
– 信息码元序列＋监督码元→编码码组
• 信道译码过程：
– 编码码组→检错或纠错→信息码元序列
2
1. 线性分组码的概念
1 0 0
G＝0 1 0 0 1 1
1 0 1
0 0 1 1 1 0
1 1 0
1 1 1
7
由式
，得码组矩阵为：
0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1 1 0
0 C＝0
1
1 1 0
0 1
0
1 0 0
0 1 0
0 0 1
1 0 1
0 1 1
110＝100
1 1 0
0 1 0
0 1 1
6
有缘学习更多＋谓ｙｇｄ３０７６考证资料或关注桃报：奉献教育（店铺）
例8-1 已知(6,3)码的生成矩阵为G，试求：(1) 编码码组 和各码组的码重；(2) 最小码距 d及min其差错控制能力。
解
(1) 由3位码组成的信息码组矩阵为D：
0 0
0 0
0 1
0 1 0
1 0 0 1 0 1
0 1 1
D＝
ck = dk
ck +1 ck+2
= =
h11d1 h12d2 h1k dk h21d1 h22d2 h2k dk
G生成矩阵
cn = hm1d1 hm2d2 hmk dk
5
写成矩阵形式，有 C = D G ，G为生成矩阵(k*n)，且：

第3章 线性分组码

由上式经移项运算，解出监督位为
a2 a6 a5 a4 a1 a 6 a 5 a 3 a0 a6 a4 a3
已知信息位后，就可直接计算出监督位。由此得出16个许用码组 表4-5（7，4）汉明码的许用码组 信息码 a6a5a4a3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 监督码 a2a1a0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 信息码 a6a5a4a3 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 监督码 a2a1a0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1
§3.2 码的一致校验矩阵与生成矩阵
一、 码的校验矩阵与生成矩阵
– ［n ，k ，d］分组码的编码问题就是在n 维 线性空间Vn 中，如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn ，k 。 – 或者说， 在满足给定条件(码的最小距离d或 码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。
• 二进制(5,3)码
– K位信息空间23
• • • • • • • • 000 001 010 011 100 101 110 111
n位编码空间25
00000 00100 01000 01100 10000 10100 11000 11100 00001 00101 01001 01101 10001 10101 11001 11101 00010 00110 01010 01110 10010 10110 11010 11110 00011 00111 01011 01111 10011 10111 11011 11111

信息论与编码民大09-线性分组码


2013/6/28
23/52
例: 已知(7,4)线性系统码的监督矩阵为
2013/6/28
24/52
线性分组码的编码实现电路

(n,k) 线性码的编码就是根据线性码的监督矩阵或生成矩 阵将长为 k 的信息组变换成长为 n(n>k) 的码字。

利用监督矩阵构造 (7,3) 线性分组码的编码电路：

最小距离dmin：(n,k) 线性码中，任意两个码字间距离的最小 值，叫码的最小距离。

最小距离是衡量码的抗干扰能力（检、纠错能力）的重 要参数。最小距离越大，抗干扰能力就越强。

汉明球：汉明球是以码字C为中心，半径为 t ，并与 C 的 汉明距离≤ t 的全体向量集合。

任意两个汉明球不相交最大程度取决于任意两个码字之 间的最小汉明距离dmin 。


2013/6/28
16/52
线性分组码的生成矩阵
线性码的封闭性:

线性码的封闭性：线性码任意两个码字之和仍是 一个码字。
因为：若 U 和 V 为线性码的任意两个码字，故有
HUT=0T，HVT=0T 那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T 即 U+V 满足监督方程，所以 U+V 一定是一个

说明约束起了作用，但还不够，需要进一步引入其它 约束
2013/6/28
5/52
对信道编码的一般要求是：
①纠错检错能力强； ②信息传输率高； ③编码规律简单，实现设备简单且费用合理； ④与信道的差错统计特性相匹配。
2013/6/28为两步：

把信息序列按一定长度分成若干信息码组，每组由 k 位组成； 编码器按照预定的线性规则(可由线性方程组规定)， 把信息码组变换成 n 重 (n>k) 码字，其中 (n－k) 个 附加码元是由信息码元的线性运算产生的。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
C = (1)
这种线性组合特征正是线性分组码名称的来历。研究线性分组码的关键是研究基底、子空间和映射规则，可把码空间与映射的关系化成如图1所示图形。
用 表示第i个基底并写成1 × n矩阵形式
＝[ ] (2)
再将k个基底排成k行n列的G矩阵，得
＝ (3)
对照式（1）可得
C＝[ ]＝ + = m否与G的行矢量正交，即式（8）是否成立。此处
G = = [ ] + [ ] = [ ] + [ ] = 0 (10)
式中，两个相同的矩阵模2相加后为全零矩阵。这就说明了Ｈ确是校验矩阵。
四、MATLAB源代码
%已知生成矩阵G，可以求出校验矩阵H。
G=[1,0,0,1,1,1;0,1,0,1,1,0;0,0,1,0,1,1];
fprintf('生成的码集为：C=\n');
disp(C);
r=input('输入码字r:');
if(r*H'==0);
r
fprintf('是码字\n');
else
r
fprintf('不是码字\n');
end;
五、结果截图
信息论课程设计
一、所选题目
已知二元（6,3）线性分组码的系统生成矩阵，计算其校验矩阵H、消息与码集的映射关系，并对任意给定的二元6重矢量判断其是否为码字。
二、题目要求
1）计算校验矩阵
2）生成消息组
3）生成码集
4）判断输入的二元6重是否为码字
三、理论分析
线性分组码码空间Ｃ是由k个线性无关的基底 , … , 张成的k维n重子空间，码空间的所有元素（即码字）都可以写成k个基底的线性组合，即
G = [ P ] = (5)
这里p是k×(n-k)矩阵； 是k×k单位矩阵，从而保证了矩阵的秩是k。
信息组m乘以系统形式的生成矩阵G后所得的码字，其前k位由单位矩阵 决定，一定与信息组各码元相同，而其余的n-k位是k个信息位的线性组合，叫做冗余位或者一致校验位。这种把信息组原封不动的搬到码字前k位的码叫做系统码，其码字具有如下形式：
基底不是唯一的，生成矩阵也不是唯一的。事实上，将k个基地线性组合后产生令一组k个矢量，只要满足线性无关性的条件，依然可以作为基底张成一个码空间。不同的基底有可能生成同一码集，但因为编码涉及码集和映射两个因素，码集一样儿映射方法不同也不能说是相同的码。
基底的线性组合等效于生成矩阵G的运算，可以产生一组新的基底。利用这点可使生成矩阵具有以下的“系统形式”：
C = ( ) =（
反之，不具备“系统”特点的码叫做非系统码。非系统码与系统码并无本质的去北欧，它的生成矩阵通过行运算转变为系统形式，这个过程叫做系统化。系统化不改变码集，只改变映射规则。
由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。因此，（n,k）线性码的任意码字c一定正交于其对偶码的任一码字，也必定正交于校验矩阵H的任意一个行矢量，即
式中m = [ ]是1 x k的信息元矩阵， = [ ]，i = 0，…，k-1是G中第i行的矢量，也是张成码空间的第i个基底，同时也是码空间元素即码字之一。由于k个基底即Ｇ的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定之后，码字仅由G矩阵决定，因此称k×n矩阵G为该（n,k）线性分组码的生成矩阵。
c = 0 (7)
式中，0代表零阵，它是[1×n] ×[n×(n-k)] = 1×(n-k)全零矢量。式（7）用以检验一个n重矢量是否为码字：若等式成立（得零矢量），该n重必为码字，否则不是码字。
G (8)
这里，0表示一个尺寸为[k ×n] ×[n×(n-k)] = k×(n-k)的零矩阵。
对于生成矩阵符合式（5）的系统码，其校验矩阵也是规则的，必为
P=[G(1:3,4:6)];
H=[P',eye(3)];
fprintf('效验矩阵为：H=\n');
disp(H);
M=eye(8,3);%消息组矩阵
p=1;
for i=0:1
for j=0:1
for k=0:1
M(p,:)=[i,j, k];
p=p+1;
end
end
end
C=mod((M*G),2);