第7章_软件编码

第7章 线性分组码习 题1. 已知一个(5, 3)线性码C 的生成矩阵为：11001G 011010111⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦（1）求系统生成矩阵；（2）列出C 的信息位与系统码字的映射关系；（3）求其最小Hamming 距离，并说明其检错、纠错能力； （4）求校验矩阵H ；（5）列出译码表，求收到r =11101时的译码步骤与译码结果。

2．设（7, 3）线性码的生成矩阵如下010101000101111001101G ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦（1）求系统生成矩阵；（2）求校验矩阵； （3）求最小汉明距离； （4）列出伴随式表。

3．已知一个(6, 3)线性码C 的生成矩阵为：.0 1 1 1 0 01 1 0 0 1 01 0 10 0 1G ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=（1） 写出它所对应的监督矩阵H ；（2） 求消息M =(101)的码字；（3） 若收到码字为101010，计算伴随式，并求最有可能的发送码字。

4．设(6, 3)线性码的信息元序列为x 1x 2x 3，它满足如下监督方程组⎪⎩⎪⎨⎧=++=++=++000631532421x x x x x x x x x （1）求校验矩阵，并校验10110是否为一个码字；（2）求生成矩阵，并由信息码元序列101生成一个码字。

习题答案1. 已知一个(5, 3)线性码C 的生成矩阵为：11001G 011010111⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦（1）求系统生成矩阵；（2）列出C 的信息位与系统码字的映射关系；（3）求其最小Hamming 距离，并说明其检错、纠错能力； （4）求校验矩阵H ；（5）列出译码表，求收到r =11101时的译码步骤与译码结果。

解：（1）线性码C 的生成矩阵经如下行变换：23132110011001101101011010011100111100111001101101010100011100111⎡⎤⎡⎤⎢⎥⎢⎥−−−−−−→⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎡⎤⎡⎤⎢⎥⎢⎥−−−−−−→⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦将第、加到第行将第加到第行得到线性码C 的系统生成矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=111000*********S G （2）码字),,,(110-=n c c c c 的编码函数为[][][]111000*********)(210m m m m f c ++==生成了的8个码字如下(3) 最小汉明距离d =2，所以可检1个错，但不能纠错。

1设计下列伪码程序的语句覆盖和路径覆盖测试用例：STARTINPUT(A,B,C)IF A>5THEN X=10ELSE X=1END IFIF B>10THEN Y=20ELSE Y=2END IFIF C>15THEN Z=30ELSE Z=3END IFPRINT(X,Y,Z)STOP答：（1）语句覆盖的测试用例因为每个判定表达式为真或为假时均有赋值语句，为了使每个语句都至少执行一次，总共需要两组测试数据，以便使得每个判定表达式取值为真或为假各一次。

下面是实现语句覆盖的典型测试用例：l使3个判定表达式之值全为假输入：A=1,B=1,C=1预期的输出：X=1,Y=2,Z=3l使3个判定表达式之值全为真输入：A=20,B=40,C=60预期的输出：X=10,Y=20,Z=30（2）路径覆盖的测试用例本程序共有8条可能的执行通路，为做到路径覆盖总共需要8组测试数据。

下面是实现路径覆盖的典型测试用例：l3个判定表达式之值全为假输入：A=1,B=1,C=1预期的输出：X=1,Y=2,Z=3l3个判定表达式依次为假、假、真输入：A=1,B=1,C=60预期的输出：X=1,Y=2,Z=30l3个判定表达式依次为假、真、假输入：A=1,B=40,C=1预期的输出：X=1,Y=20,Z=3l3个判定表达式依次为假、真、真输入：A=1,B=40,C=60预期的输出：X=1,Y=20,Z=30l3个判定表达式依次为真、假、假输入：A=20,B=1,C=1预期的输出：X=10,Y=2,Z=3l3个判定表达式依次为真、假、真输入：A=20,B=1,C=60预期的输出：X=10,Y=2,Z=30l3个判定表达式依次为真、真、假输入：A=20,B=40,C=1预期的输出：X=10,Y=20,Z=3l3个判定表达式全为真输入：A=20,B=40,C=60预期的输出：X=10,Y=20,Z=302设计下列伪码程序的分支覆盖和条件组合覆盖测试用例：STARTINPUT(A,B,C,D)IF (A>0) AND (B>0)THEN X=A+BELSE X=A-BEND IFIF (C>A) OR (D<B)THEN Y=C-DELSE Y=C+DEND IFPRINT(X,Y)STOP答：（1）分支覆盖（即判定覆盖）标准为，不仅使每个语句至少执行一次，而且使每个判定表达式的每个分支都至少执行一次。

第7 章 軟體測試技術
7.2.3 白盒測試方法 白盒測試也稱結構測試或邏輯驅動測試。在使 用白盒測試方案時，測試者必須檢查程式的 內部結構，從檢查程式的邏輯著手，對所有 邏輯路徑進行測試，得出測試數據。 開始 1 ．邏輯覆蓋法：以程式內部的邏輯結構為基礎 的測試用例設計技術。 X=x/a a>1andb= 0 （1）語句覆蓋 X=x+1 A = 2 o r （2）判定覆蓋 x>1 （3）條件覆蓋 輸出a,b,x
第7 章 軟體測試技術
3．錯誤推測法
錯誤推測法是基於經驗和直覺推測程式中所 有可能存在的各種錯誤，從而有針對性的 設計測試用例的方法。
第7 章 軟體測試技術
4．因果圖方法 (1) 分析軟體規格說明描述中，哪些是原因(即輸入條件 或輸入條件的等價類 )，哪些是結果 (即輸出條件 ) ， 並給每個原因和結果賦予一個識別字。 (2) 分析軟體規格說明描述中的語義，找出原因與結果之 間、原因與原因之間對應的關係，根據這些關係，畫 出因果圖。 (3) 由於語法或環境限制，有些原因與原因之間，原因與 結果之間的組合情況不可能出現。為表明這些特殊情 況，在因果圖上用一些記號表明約束或限制條件。 (4) 把因果圖轉換為判定表。 (5) 把判定表的每一列拿出來作為依據,設計測試用例
第7 章 軟體測試技術
7.1.2 軟體測試原則 1. 應早並不斷地進行測試 2. 程式員應盡可能避免檢查自己的程式 3. 測試用例應當包括合理的輸入條件和 不合理的輸入條件 4. 測試用例應包括輸入數據和預期的輸 出結果兩部分 5. 全面檢查每個測試結果 6. 嚴格按照測試計畫來測試 7. 充分注意測試中的集群現象 8. 注意遵守“經濟性”的原則
第7 章 軟體測試技術
3）根據規格說明的每個輸出條件，使用前面的原則 1）。 4）根據規格說明的每個輸出條件，應用前面的原則 2）。 5）如果程式的規格說明給出的輸入域或輸出域是有序集 合，則應選取集合的第一個元素和最後一個元素作 為測試用例。 6）如果程式中使用了一個內部數據結構，則應當選擇這 個內部數據結構的邊界上的值作為測試用例。 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的一个基