简介这是信息论与编码曹雪虹第六章课后习题答案PDF适合通信工程、电子信息等专业本科生复习“信道编码与线性分组码”时参考。内容以第六章习题6-1、6-3、6-4、6-5、6-6为主线覆盖差错符号与差错图样、纠错码分类、矢量空间与对偶空间、生成矩阵与校验矩阵、伴随式与标准阵列译码表、最小码距与纠错能力等核心知识点并对系统性循环码的生成多项式与校验多项式作了梳理。其中二元域上矢量空间元素个数、系统码生成矩阵与校验矩阵的推导、最小码距判定等难点均有逐步解答便于对照教材逐题消化。资源共1个PDF文件压缩包约29KB便于下载后直接阅读或打印。已有1215人浏览学习。对正在准备期末考或考研复习的读者而言借助这些习题推导和矩阵例题可以更扎实地理解编码定理与线性分组码构造方法节省大量整理答案的时间。1. 第六章课后题为什么翻答案也救不了你曹雪虹《信息论与编码》的第六章多数院校的教学进度都把它放在信道编码这一块线性分组码、循环码、卷积码三座大山。课后习题答案单独看几乎每步都对但合上书自己推一遍最容易翻车的地方往往不是概念而是矩阵转置多转了一次、多项式除法补零补错位、维特比回溯忘了从哪条路径回去这类计算细节。这篇我就按第六章最常见的三类计算题把从生成矩阵到校正子、从生成多项式到余式、从网格图到幸存路径的完整流程拆开讲每一段都给出可以直接套用的手算模板和验证代码目标是让你做题时不只对得上答案还知道答案为什么是它。2. 线性分组码从生成矩阵到校正子的完整计算模板2.1 先把 G、H、d_min 三者的关系定住线性分组码的习题几乎都围绕(n, k)码的三个要素转生成矩阵Gk 行 n 列、校验矩阵Hn-k 行 n 列、最小汉明距离d_min。三者之间有两个必须背熟的约束第一G和H的行空间正交也就是G * H^T 0这个恒等式是所有“验证生成矩阵写得对不对”的根。第二d_min等于H中线性相关的最小列数对最常见的汉明码来说d_min 3能纠 1 位错、检 2 位错。很多题给了一个H然后问能纠几位错本质就是在问d_min的下界而不是让你把每个码字都枚举出来。教材里常用系统码形式即G [I_k | P]对应H [P^T | I_{n-k}]。注意二元域上减法和加法等价所以写H的时候不用考虑负号。这个约定式的好处是信息位直接落在码字的前 k 位答(7,4)汉明码编码结果时直接抄信息位再加校验位就行。下面用(7,4)汉明码做全文的统一例子它的G和H如下矩阵内容G[1 0 0 0 1 1 0; 0 1 0 0 1 0 1; 0 0 1 0 0 1 1; 0 0 0 1 1 1 1]H[1 1 0 1 1 0 0; 1 0 1 1 0 1 0; 0 1 1 1 0 0 1]我一般建议先验证G * H^T 0再拿题里的码字去乘H^T。验证通过后面所有步骤才有意义。2.1.1 常见汉明码参数速查表mn 2^m - 1k n - md_min纠错能力 t3743141511315312631考试里出现(7,4)和(15,11)的概率最高。看到(15,11)不要慌它和(7,4)的差别只是 H 的列变成了 4 位二进制数校正子定位错误位置的逻辑完全一样。2.2 用 GF(2) 矩阵乘法验算 G 和 H算G * H^T时最容易犯的错是把普通乘法规则带进来。GF(2) 上加法是异或乘法是与运算。你可以手算也可以用下面这段纯 Python 代码做验算def gf2_mat_mul(A, B): # A 为 r x mB 为 m x c返回 r x c r, m1 len(A), len(A[0]) m2, c len(B), len(B[0]) assert m1 m2, 矩阵维度不匹配 C [[0] * c for _ in range(r)] for i in range(r): for j in range(c): s 0 for k in range(m1): s ^ A[i][k] B[k][j] # 乘是 AND加是 XOR C[i][j] s return C G [ [1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1], ] H [ [1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1], ] HT [[H[r][c] for r in range(len(H))] for c in range(len(H[0]))] print(gf2_mat_mul(G, HT)) # 输出 4x3 全零矩阵这段代码里最核心的一行是s ^ A[i][k] B[k][j]它同时完成了乘法和加法也正是手算时最容易漏掉“异或”的地方。输出如果是全零矩阵说明你手里的 G 和 H 确实是同一个码的生成矩阵与校验矩阵后面算校正子才有意义。如果你从题里抄来的 G 和 H 验证不过先别急着往下算多半是转了置或者漏了一列。2.3 校正子 S rH^T 的习题常考动作接收端拿到向量 r 后第一步永远是算校正子S r * H^T (维度 1 x (n-k))S 为全零说明 r 是合法码字直接取前 k 位就是信息位。S 非零说明有错而且对汉明码这类单纠错码来说S 这个列向量恰好等于 H 中某一列那一列的序号就是出错位置。这是第六章简答题和计算题最密集的考点。沿用前面的 (7,4) 汉明码假设发送码字为1100011信息位 1100 编码得到接收端收到1110011也就是第 3 位发生了翻转。逐位算S (1,1,1,0,0,1,1) * H^T (0, 1, 1)H的第 3 列恰好是(0,1,1)于是判定第 3 位出错把它从 1 翻回 0得到正确码字1100011信息位恢复为1100。整个过程在考试里必须写成“S …等于 H 的第 3 列故第 3 位出错”这 3 个步骤漏掉任何一步都会扣分。2.3.1 校正子定位错误位置的代码实现def syndrome(r, H): # r 是长度 n 的接收向量返回长度 n-k 的校正子 return gf2_mat_mul([r], H)[0] r [1,1,1,0,0,1,1] S syndrome(r, H) print(S) # [0, 1, 1] for idx, col in enumerate(HT, start1): if col S: print(错误位置:, idx) # 错误位置: 3HT是 H 的转置它的每一行正好对应 H 的一列。枚举时用start1是因为教材和试卷里码字位置从 1 开始编号。注意这里能直接“按列号定位错误位”的前提是 H 的列互不相同汉明码满足这个性质一般线性分组码则不一定遇到非汉明码时 S 非零只能说明有错不能直接确定是哪一位。2.4 两个容易被扣分的隐藏考点一是标准阵与陪集首。有些题给一个 (6,3) 码并列出 8 个陪集首让你译码一个接收序列本质还是算 S再在标准阵里找 S 所在列与陪集首行的交叉点。别被“标准阵”三个字吓住它就是把所有 2^(n-k) 个可纠正错误图样按校正子分组定位逻辑和汉明码完全一致只是 H 的列不一定唯一所以需要查表而不是直接对列号。二是d_min与纠错能力的关系能纠 t 位错的前提是d_min 2t 1。做题时如果题目问“这个码能不能纠 2 位错”先算t floor((d_min - 1) / 2)不要凭感觉回答。第六章的答案里经常出现“不能因为 d_min 3 5”这种结论丢分点往往不是不会算 d_min而是忘了把这个不等式写出来。3. 循环码生成多项式与系统码编解码手算流程3.1 循环码的本质码字与多项式的互相表示循环码是线性分组码的子集多了一个“循环移位后仍是码字”的约束。第六章里遇到循环码习题第一步就是把所有向量写成多项式1101写成x^3 x^2 1系数的位置就是向量位的位置。这个转换本身不值钱但它决定了后面所有长除、求余、整除判断的方向。循环码的关键参数是生成多项式g(x)它必须满足两个条件次数等于n - k并且能整除x^n 1。题目一般直接给出g(x)但偶尔会倒过来问“验证某个多项式能不能做 (7,4) 循环码的生成多项式”这时你就去做x^7 1对g(x)的整除余数为零才是合法的。注意x^7 1的系数写法是10000001不是1000001这种位数错位是手算丢分重灾区。3.2 系统码编码m(x)·x^(n-k) mod g(x) 的手算与代码系统码的编码套路固定信息多项式m(x)左移n-k位得到m(x)·x^(n-k)再除以g(x)取余式余式就是校验位最后拼到信息位后面。以(7,4)循环码、g(x) x^3 x 1二进制1011、信息1010为例m(x)·x^3 x^6 x^4 → 二进制 1010000 1010000 除以 1011长除过程 1010000 ⊕ 1011000 0001000 商第1位为1 0001000 商第2位为0 0001000 ⊕ 0001011 0000011 商第4位为1余式是011即校验位011所以码字为1010011。长除的要点是每次对齐被除数当前最高位与除式最高位异或后把后面的位落下来中间出现前导 0 时直接商 0不需要动余数。很多人在“补零”这一步出错被除式左移之后低位补 0除式异或时也要保持等长不能把除式右移对齐。下面这段代码把 GF(2) 多项式除法封装成函数可以反复用来验证手算结果def gf2_poly_mod(dividend, divisor): # dividend 和 divisor 都是整数bit i 表示 x^i 的系数 deg_g divisor.bit_length() - 1 r dividend while r ! 0 and r.bit_length() - 1 deg_g: r ^ divisor ((r.bit_length() - 1) - deg_g) return r g 0b1011 # x^3 x 1 info 0b1010 # 信息多项式 rem gf2_poly_mod(info 3, g) print(bin(rem)) # 0b11对应 011 code (info 3) | rem print(gf2_poly_mod(code, g)) # 0说明整除编码正确代码里最关键的是divisor ((r.bit_length() - 1) - deg_g)它把除式对齐到被除式的最高位模拟手算时“除式左移与被除数对齐”的动作。验证整除时结果为 0说明code(x)确实是g(x)的倍式这个性质是所有循环码检错的基础。3.3 接收端检错余式非零即出错但别急着定位接收端把收到的多项式r(x)除以g(x)余式为零则代表接收码字合法。注意这里只能判断“有没有错”不能定位错在哪一位。很多同学把线性分组码“校正子直接对应错误位置”的思维搬过来看到循环码余式非零就想定位这是第六章最常见的概念混淆。循环码的进一步纠错通常要用到伴随式与错误图样的对应表。习题里常见的考法是给一个接收码字1100011和g(x)1011让你判断是否出错。算除法余式非零就回答“有错”再用标准阵列或查表确定错误位置。如果题目只让检错不要画蛇添足去纠正答多了反而暴露对概念边界不清晰。3.3.1 除法余式的快速验证命令不需要 IDE命令行里用 Python 一行也能算python3 -c def mod(a,b): while a and a.bit_length()-1 b.bit_length()-1: a ^ b (a.bit_length()-1-(b.bit_length()-1)) return a print(bin(mod(0b1100011, 0b1011))) 把接收码字直接作为被除式代入余数非零就说明途中出了错。这套多项式除法的实现思路在 CRC 校验里也是一模一样的学会循环码的长除等于顺手把计算机网络里的 CRC 计算也掌握了。3.4 习题里高频出现的 g(x) 与常用校验多项式速查第六章课后题给的多项式来来去去就那几个背下来能省大量验算时间码型生成多项式二进制参数(7,4) 循环码x^3 x 11011纠 1 位错(7,3) 循环码x^4 x^2 x 110111纠 2 位错CRC-8x^8 x^2 x 1100000111检错用CRC-16-CCITTx^16 x^12 x^5 110001000000100001检错用看到(7,3)时注意它的n-k4所以 g(x) 次数是 4校验位是 4 位不要再套 (7,4) 的 3 位校验。一个常见的偷懒检查手段是算出来的校验位位数必须等于n-k如果不对回头检查是不是除式没对齐或除式写错。4. 卷积码状态图、网格图与维特比译码手算4.1 (2,1,3) 卷积码的生成与编码卷积码和分组码最大的区别是编码输出与当前输入和之前若干个输入都有关因此编码器有记忆。第六章常用的例子是(2,1,3)卷积码码率R 1/2约束长度 3记忆深度为 2。两个生成序列分别是g1 111、g2 101也就是生成多项式形式的G1(D) 1 D D^2、G2(D) 1 D^2。编码规则用移位寄存器最好理解寄存器存最近两个输入比特s1 s2输入为u时两路输出分别是c1 u ⊕ s1 ⊕ s2 c2 u ⊕ s2每输入一个比特输出两个比特随后寄存器右移新输入进入s1原s1移到s2。以输入u 1011为例编码过程如下初始状态 00 u1: c11, c21 → 输出 11状态变 10 u0: c11, c20 → 输出 10状态变 01 u1: c10, c20 → 输出 00状态变 10 u1: c10, c21 → 输出 01状态变 11编码输出是11 10 00 01。注意最后不要立刻结束编码器寄存器里还残留着最后两个输入比特如果直接收尾译码端会丢失尾部信息所以末尾要补两个 0 让状态归零这个过程叫 flush。补零后还会额外输出 4 个比特答案里多出来的那几位就是这么来的。def conv_encode(bits, g10b111, g20b101, m2): reg [0] * m out [] for b in bits [0] * m: # 末尾补 m 个 0 c1 b ^ reg[0] ^ reg[1] c2 b ^ reg[1] out [c1, c2] reg [b] reg[:-1] return out print(conv_encode([1,0,1,1])) # [1,1,1,0,0,0,0,1,0,1,1,1]这段代码里的reg [b] reg[:-1]就是寄存器右移丢掉最老的比特。输出结果与手算一致末尾的01 11就是 flush 产生的尾比特。4.1.1 状态转移表网格图的查表基础维特比译码要在网格图上做而网格图的每一段弧都由状态转移表决定。上面这个 (2,1,3) 码的完整状态转移如下当前状态 s1s2输入 u下一状态输出 c1c200000000011011010001101110001000110101110111001011111110做题时这张表现场画出来最保险不要死记因为不同的生成多项式会得到不同的转移表。画法也很机械当前状态和输入一起决定下一状态和输出逐行填即可两分钟就能画完。4.2 维特比译码路径度量、幸存路径、回溯三步走维特比译码是按时刻推进的动态规划。每个状态在每时刻保留一条度量最小的路径称为幸存路径度量通常用接收序列与该路径对应编码输出的汉明距离累加。核心步骤只有三步初始化t0 时状态 00 的度量是 0其余状态是无穷大。逐步扩展对每个当前状态和两个输入分支计算下一状态的候选度量每个下一状态保留最小候选并记录来源状态和输入比特。回溯所有时刻走完后取终态度量最小的状态按记录的来源逐时刻回退得到译码比特序列。最容易出错的是第二步里的“每状态保留一条”。很多人会保留所有到达同一状态的分支导致路径数量指数爆炸这是对维特比“剪枝”本质理解不到位。网格图里每个时刻状态数是固定的2^mm 是记忆深度所以存储量随时间线性增长这恰恰是维特比算法能实用的原因。4.3 一个带 1 位错误的完整译码例子沿用上面的编码器发送信息1011编码输出是11 10 00 01假设信道把第 2 时刻的10翻成11接收序列变为11 11 00 01。下面给出每个时刻四个状态的幸存度量括号内是“来源状态, 输入比特”时刻 / 接收状态 00状态 01状态 10状态 11t00∞∞∞t1: 112 (00,0)∞0 (00,1)∞t2: 114 (00,0)1 (10,0)2 (00,1)1 (10,1)t3: 003 (01,0)2 (11,0)1 (01,1)2 (11,1)t4: 013 (01,0)2 (11,0)3 (01,1)1 (10,1)t4 结束时状态 11 的度量只有 1是全网格最小值。从状态 11 开始回溯t4 的来源是 (10,1)t3 状态 10 的来源是 (01,1)t2 状态 01 的来源是 (10,0)t1 状态 10 的来源是 (00,1)。把输入比特按时间顺序排出来是1, 0, 1, 1正是原始信息。这演示了维特比即使在一路接收出错的情况下仍然能通过累积度量找到全局最优路径。下面这段代码把回溯过程显式写出来适合考试后自查# surv[t][state] (prev_state, input_bit) surv { 1: {0b00: (0b00, 0), 0b10: (0b00, 1)}, 2: {0b00: (0b00, 0), 0b10: (0b00, 1), 0b01: (0b10, 0), 0b11: (0b10, 1)}, 3: {0b00: (0b01, 0), 0b10: (0b01, 1), 0b01: (0b11, 0), 0b11: (0b11, 1)}, 4: {0b00: (0b01, 0), 0b10: (0b01, 1), 0b01: (0b11, 0), 0b11: (0b10, 1)}, } bits [] state 0b11 # 选终态度量最小的状态 for t in range(4, 0, -1): prev, u surv[t][state] bits.append(u) state prev print(bits[::-1]) # [1, 0, 1, 1]代码里的surv字典就是考试卷面画网格图时需要保留的信息每个时刻每个状态只记一条来源和对应的输入比特。回溯时从最后一个时刻往前推得到的比特序列反转一下就是译码结果。4.4 flush bit为什么答案末尾总多出几个 0 或 1很多第六章习题的卷积码编码问“输出序列是什么”答案末尾会多几位这几位就是 flush 产生的。规范做法是信息位后面补记忆深度个 0再继续编码最后丢弃这几位 0 对应的输入只保留输出。上面例子中信息只有 4 位但完整输出是 12 位比4 × 2 8位多了 4 位多出来的就是两个 flush 周期产生的输出。考试时如果只要求编码看清题目有没有说“编码器初始状态为零、末尾需要归零”。如果没提默认也要做因为不做 flush 的话译码端无法确定最终状态维特比回溯就没有合法的终止节点。做题时在编码过程的最后补两个 0能避免丢掉最后两个信息比特的编码输出。5. 对答案之外三个能自查的硬技巧5.1 最小码距 d_min 用暴力枚举兜底题目给一个未知生成矩阵让你求 d_min 并判断纠错能力最稳妥的办法是对所有非零信息向量编码统计码字最小重量。def min_distance(G): k, n len(G), len(G[0]) d n for mask in range(1, 1 k): c [0] * n for i in range(k): if (mask i) 1: c [c[j] ^ G[i][j] for j in range(n)] d min(d, sum(c)) return d G [ [1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1], ] print(min_distance(G)) # 3线性分组码的最小距离等于非零码字的最小重量所以枚举后直接取最小汉明重量即可。这个办法对 (7,4) 这种小参数码非常快在考场上也适合用来验证自己通过 H 列相关性推断出的 d_min 是否正确。5.2 译码结果用编码器回读一遍维特比译码完成后把译出的比特序列送进编码器重新编码比对输出与接收序列的汉明距离应该正好等于幸存路径的最终度量。如果对不上八成是回溯方向反了或者终态选错。这个回读检查同样适用于线性分组码纠正后的码字乘 H^T 必须得到全零向量否则说明错误位置定位错了。5.3 多项式余式为零的快速验证循环码题目做到最后一步“验证码字合法”直接用gf2_poly_mod对完整码字求余余数为零就收工。这里有个小技巧不要把校验位拼回去之后又重新手算一遍长除而是用编码时的中间结果——编码时已经算过code (info (n-k)) | rem整除性是构造时就保证的接收端想验证的是另一件事即收到的序列去掉尾部的校验位后重新编码得到的结果是否和收到的校验位一致或者直接对完整接收序列求余。两种做法等价选计算量小的一种即可。对接收序列求余时如果余数不为零再回头看看是不是信号里把x^n 1的因子弄混了常见的坑是把g(x)的次数当成n-k1导致补位差一位。本文还有配套的精品资源点击获取 线性分组码、循环码与卷积码手算模板：从生成矩阵到维特比译码
简介这是信息论与编码曹雪虹第六章课后习题答案PDF适合通信工程、电子信息等专业本科生复习“信道编码与线性分组码”时参考。内容以第六章习题6-1、6-3、6-4、6-5、6-6为主线覆盖差错符号与差错图样、纠错码分类、矢量空间与对偶空间、生成矩阵与校验矩阵、伴随式与标准阵列译码表、最小码距与纠错能力等核心知识点并对系统性循环码的生成多项式与校验多项式作了梳理。其中二元域上矢量空间元素个数、系统码生成矩阵与校验矩阵的推导、最小码距判定等难点均有逐步解答便于对照教材逐题消化。资源共1个PDF文件压缩包约29KB便于下载后直接阅读或打印。已有1215人浏览学习。对正在准备期末考或考研复习的读者而言借助这些习题推导和矩阵例题可以更扎实地理解编码定理与线性分组码构造方法节省大量整理答案的时间。1. 第六章课后题为什么翻答案也救不了你曹雪虹《信息论与编码》的第六章多数院校的教学进度都把它放在信道编码这一块线性分组码、循环码、卷积码三座大山。课后习题答案单独看几乎每步都对但合上书自己推一遍最容易翻车的地方往往不是概念而是矩阵转置多转了一次、多项式除法补零补错位、维特比回溯忘了从哪条路径回去这类计算细节。这篇我就按第六章最常见的三类计算题把从生成矩阵到校正子、从生成多项式到余式、从网格图到幸存路径的完整流程拆开讲每一段都给出可以直接套用的手算模板和验证代码目标是让你做题时不只对得上答案还知道答案为什么是它。2. 线性分组码从生成矩阵到校正子的完整计算模板2.1 先把 G、H、d_min 三者的关系定住线性分组码的习题几乎都围绕(n, k)码的三个要素转生成矩阵Gk 行 n 列、校验矩阵Hn-k 行 n 列、最小汉明距离d_min。三者之间有两个必须背熟的约束第一G和H的行空间正交也就是G * H^T 0这个恒等式是所有“验证生成矩阵写得对不对”的根。第二d_min等于H中线性相关的最小列数对最常见的汉明码来说d_min 3能纠 1 位错、检 2 位错。很多题给了一个H然后问能纠几位错本质就是在问d_min的下界而不是让你把每个码字都枚举出来。教材里常用系统码形式即G [I_k | P]对应H [P^T | I_{n-k}]。注意二元域上减法和加法等价所以写H的时候不用考虑负号。这个约定式的好处是信息位直接落在码字的前 k 位答(7,4)汉明码编码结果时直接抄信息位再加校验位就行。下面用(7,4)汉明码做全文的统一例子它的G和H如下矩阵内容G[1 0 0 0 1 1 0; 0 1 0 0 1 0 1; 0 0 1 0 0 1 1; 0 0 0 1 1 1 1]H[1 1 0 1 1 0 0; 1 0 1 1 0 1 0; 0 1 1 1 0 0 1]我一般建议先验证G * H^T 0再拿题里的码字去乘H^T。验证通过后面所有步骤才有意义。2.1.1 常见汉明码参数速查表mn 2^m - 1k n - md_min纠错能力 t3743141511315312631考试里出现(7,4)和(15,11)的概率最高。看到(15,11)不要慌它和(7,4)的差别只是 H 的列变成了 4 位二进制数校正子定位错误位置的逻辑完全一样。2.2 用 GF(2) 矩阵乘法验算 G 和 H算G * H^T时最容易犯的错是把普通乘法规则带进来。GF(2) 上加法是异或乘法是与运算。你可以手算也可以用下面这段纯 Python 代码做验算def gf2_mat_mul(A, B): # A 为 r x mB 为 m x c返回 r x c r, m1 len(A), len(A[0]) m2, c len(B), len(B[0]) assert m1 m2, 矩阵维度不匹配 C [[0] * c for _ in range(r)] for i in range(r): for j in range(c): s 0 for k in range(m1): s ^ A[i][k] B[k][j] # 乘是 AND加是 XOR C[i][j] s return C G [ [1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1], ] H [ [1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1], ] HT [[H[r][c] for r in range(len(H))] for c in range(len(H[0]))] print(gf2_mat_mul(G, HT)) # 输出 4x3 全零矩阵这段代码里最核心的一行是s ^ A[i][k] B[k][j]它同时完成了乘法和加法也正是手算时最容易漏掉“异或”的地方。输出如果是全零矩阵说明你手里的 G 和 H 确实是同一个码的生成矩阵与校验矩阵后面算校正子才有意义。如果你从题里抄来的 G 和 H 验证不过先别急着往下算多半是转了置或者漏了一列。2.3 校正子 S rH^T 的习题常考动作接收端拿到向量 r 后第一步永远是算校正子S r * H^T (维度 1 x (n-k))S 为全零说明 r 是合法码字直接取前 k 位就是信息位。S 非零说明有错而且对汉明码这类单纠错码来说S 这个列向量恰好等于 H 中某一列那一列的序号就是出错位置。这是第六章简答题和计算题最密集的考点。沿用前面的 (7,4) 汉明码假设发送码字为1100011信息位 1100 编码得到接收端收到1110011也就是第 3 位发生了翻转。逐位算S (1,1,1,0,0,1,1) * H^T (0, 1, 1)H的第 3 列恰好是(0,1,1)于是判定第 3 位出错把它从 1 翻回 0得到正确码字1100011信息位恢复为1100。整个过程在考试里必须写成“S …等于 H 的第 3 列故第 3 位出错”这 3 个步骤漏掉任何一步都会扣分。2.3.1 校正子定位错误位置的代码实现def syndrome(r, H): # r 是长度 n 的接收向量返回长度 n-k 的校正子 return gf2_mat_mul([r], H)[0] r [1,1,1,0,0,1,1] S syndrome(r, H) print(S) # [0, 1, 1] for idx, col in enumerate(HT, start1): if col S: print(错误位置:, idx) # 错误位置: 3HT是 H 的转置它的每一行正好对应 H 的一列。枚举时用start1是因为教材和试卷里码字位置从 1 开始编号。注意这里能直接“按列号定位错误位”的前提是 H 的列互不相同汉明码满足这个性质一般线性分组码则不一定遇到非汉明码时 S 非零只能说明有错不能直接确定是哪一位。2.4 两个容易被扣分的隐藏考点一是标准阵与陪集首。有些题给一个 (6,3) 码并列出 8 个陪集首让你译码一个接收序列本质还是算 S再在标准阵里找 S 所在列与陪集首行的交叉点。别被“标准阵”三个字吓住它就是把所有 2^(n-k) 个可纠正错误图样按校正子分组定位逻辑和汉明码完全一致只是 H 的列不一定唯一所以需要查表而不是直接对列号。二是d_min与纠错能力的关系能纠 t 位错的前提是d_min 2t 1。做题时如果题目问“这个码能不能纠 2 位错”先算t floor((d_min - 1) / 2)不要凭感觉回答。第六章的答案里经常出现“不能因为 d_min 3 5”这种结论丢分点往往不是不会算 d_min而是忘了把这个不等式写出来。3. 循环码生成多项式与系统码编解码手算流程3.1 循环码的本质码字与多项式的互相表示循环码是线性分组码的子集多了一个“循环移位后仍是码字”的约束。第六章里遇到循环码习题第一步就是把所有向量写成多项式1101写成x^3 x^2 1系数的位置就是向量位的位置。这个转换本身不值钱但它决定了后面所有长除、求余、整除判断的方向。循环码的关键参数是生成多项式g(x)它必须满足两个条件次数等于n - k并且能整除x^n 1。题目一般直接给出g(x)但偶尔会倒过来问“验证某个多项式能不能做 (7,4) 循环码的生成多项式”这时你就去做x^7 1对g(x)的整除余数为零才是合法的。注意x^7 1的系数写法是10000001不是1000001这种位数错位是手算丢分重灾区。3.2 系统码编码m(x)·x^(n-k) mod g(x) 的手算与代码系统码的编码套路固定信息多项式m(x)左移n-k位得到m(x)·x^(n-k)再除以g(x)取余式余式就是校验位最后拼到信息位后面。以(7,4)循环码、g(x) x^3 x 1二进制1011、信息1010为例m(x)·x^3 x^6 x^4 → 二进制 1010000 1010000 除以 1011长除过程 1010000 ⊕ 1011000 0001000 商第1位为1 0001000 商第2位为0 0001000 ⊕ 0001011 0000011 商第4位为1余式是011即校验位011所以码字为1010011。长除的要点是每次对齐被除数当前最高位与除式最高位异或后把后面的位落下来中间出现前导 0 时直接商 0不需要动余数。很多人在“补零”这一步出错被除式左移之后低位补 0除式异或时也要保持等长不能把除式右移对齐。下面这段代码把 GF(2) 多项式除法封装成函数可以反复用来验证手算结果def gf2_poly_mod(dividend, divisor): # dividend 和 divisor 都是整数bit i 表示 x^i 的系数 deg_g divisor.bit_length() - 1 r dividend while r ! 0 and r.bit_length() - 1 deg_g: r ^ divisor ((r.bit_length() - 1) - deg_g) return r g 0b1011 # x^3 x 1 info 0b1010 # 信息多项式 rem gf2_poly_mod(info 3, g) print(bin(rem)) # 0b11对应 011 code (info 3) | rem print(gf2_poly_mod(code, g)) # 0说明整除编码正确代码里最关键的是divisor ((r.bit_length() - 1) - deg_g)它把除式对齐到被除式的最高位模拟手算时“除式左移与被除数对齐”的动作。验证整除时结果为 0说明code(x)确实是g(x)的倍式这个性质是所有循环码检错的基础。3.3 接收端检错余式非零即出错但别急着定位接收端把收到的多项式r(x)除以g(x)余式为零则代表接收码字合法。注意这里只能判断“有没有错”不能定位错在哪一位。很多同学把线性分组码“校正子直接对应错误位置”的思维搬过来看到循环码余式非零就想定位这是第六章最常见的概念混淆。循环码的进一步纠错通常要用到伴随式与错误图样的对应表。习题里常见的考法是给一个接收码字1100011和g(x)1011让你判断是否出错。算除法余式非零就回答“有错”再用标准阵列或查表确定错误位置。如果题目只让检错不要画蛇添足去纠正答多了反而暴露对概念边界不清晰。3.3.1 除法余式的快速验证命令不需要 IDE命令行里用 Python 一行也能算python3 -c def mod(a,b): while a and a.bit_length()-1 b.bit_length()-1: a ^ b (a.bit_length()-1-(b.bit_length()-1)) return a print(bin(mod(0b1100011, 0b1011))) 把接收码字直接作为被除式代入余数非零就说明途中出了错。这套多项式除法的实现思路在 CRC 校验里也是一模一样的学会循环码的长除等于顺手把计算机网络里的 CRC 计算也掌握了。3.4 习题里高频出现的 g(x) 与常用校验多项式速查第六章课后题给的多项式来来去去就那几个背下来能省大量验算时间码型生成多项式二进制参数(7,4) 循环码x^3 x 11011纠 1 位错(7,3) 循环码x^4 x^2 x 110111纠 2 位错CRC-8x^8 x^2 x 1100000111检错用CRC-16-CCITTx^16 x^12 x^5 110001000000100001检错用看到(7,3)时注意它的n-k4所以 g(x) 次数是 4校验位是 4 位不要再套 (7,4) 的 3 位校验。一个常见的偷懒检查手段是算出来的校验位位数必须等于n-k如果不对回头检查是不是除式没对齐或除式写错。4. 卷积码状态图、网格图与维特比译码手算4.1 (2,1,3) 卷积码的生成与编码卷积码和分组码最大的区别是编码输出与当前输入和之前若干个输入都有关因此编码器有记忆。第六章常用的例子是(2,1,3)卷积码码率R 1/2约束长度 3记忆深度为 2。两个生成序列分别是g1 111、g2 101也就是生成多项式形式的G1(D) 1 D D^2、G2(D) 1 D^2。编码规则用移位寄存器最好理解寄存器存最近两个输入比特s1 s2输入为u时两路输出分别是c1 u ⊕ s1 ⊕ s2 c2 u ⊕ s2每输入一个比特输出两个比特随后寄存器右移新输入进入s1原s1移到s2。以输入u 1011为例编码过程如下初始状态 00 u1: c11, c21 → 输出 11状态变 10 u0: c11, c20 → 输出 10状态变 01 u1: c10, c20 → 输出 00状态变 10 u1: c10, c21 → 输出 01状态变 11编码输出是11 10 00 01。注意最后不要立刻结束编码器寄存器里还残留着最后两个输入比特如果直接收尾译码端会丢失尾部信息所以末尾要补两个 0 让状态归零这个过程叫 flush。补零后还会额外输出 4 个比特答案里多出来的那几位就是这么来的。def conv_encode(bits, g10b111, g20b101, m2): reg [0] * m out [] for b in bits [0] * m: # 末尾补 m 个 0 c1 b ^ reg[0] ^ reg[1] c2 b ^ reg[1] out [c1, c2] reg [b] reg[:-1] return out print(conv_encode([1,0,1,1])) # [1,1,1,0,0,0,0,1,0,1,1,1]这段代码里的reg [b] reg[:-1]就是寄存器右移丢掉最老的比特。输出结果与手算一致末尾的01 11就是 flush 产生的尾比特。4.1.1 状态转移表网格图的查表基础维特比译码要在网格图上做而网格图的每一段弧都由状态转移表决定。上面这个 (2,1,3) 码的完整状态转移如下当前状态 s1s2输入 u下一状态输出 c1c200000000011011010001101110001000110101110111001011111110做题时这张表现场画出来最保险不要死记因为不同的生成多项式会得到不同的转移表。画法也很机械当前状态和输入一起决定下一状态和输出逐行填即可两分钟就能画完。4.2 维特比译码路径度量、幸存路径、回溯三步走维特比译码是按时刻推进的动态规划。每个状态在每时刻保留一条度量最小的路径称为幸存路径度量通常用接收序列与该路径对应编码输出的汉明距离累加。核心步骤只有三步初始化t0 时状态 00 的度量是 0其余状态是无穷大。逐步扩展对每个当前状态和两个输入分支计算下一状态的候选度量每个下一状态保留最小候选并记录来源状态和输入比特。回溯所有时刻走完后取终态度量最小的状态按记录的来源逐时刻回退得到译码比特序列。最容易出错的是第二步里的“每状态保留一条”。很多人会保留所有到达同一状态的分支导致路径数量指数爆炸这是对维特比“剪枝”本质理解不到位。网格图里每个时刻状态数是固定的2^mm 是记忆深度所以存储量随时间线性增长这恰恰是维特比算法能实用的原因。4.3 一个带 1 位错误的完整译码例子沿用上面的编码器发送信息1011编码输出是11 10 00 01假设信道把第 2 时刻的10翻成11接收序列变为11 11 00 01。下面给出每个时刻四个状态的幸存度量括号内是“来源状态, 输入比特”时刻 / 接收状态 00状态 01状态 10状态 11t00∞∞∞t1: 112 (00,0)∞0 (00,1)∞t2: 114 (00,0)1 (10,0)2 (00,1)1 (10,1)t3: 003 (01,0)2 (11,0)1 (01,1)2 (11,1)t4: 013 (01,0)2 (11,0)3 (01,1)1 (10,1)t4 结束时状态 11 的度量只有 1是全网格最小值。从状态 11 开始回溯t4 的来源是 (10,1)t3 状态 10 的来源是 (01,1)t2 状态 01 的来源是 (10,0)t1 状态 10 的来源是 (00,1)。把输入比特按时间顺序排出来是1, 0, 1, 1正是原始信息。这演示了维特比即使在一路接收出错的情况下仍然能通过累积度量找到全局最优路径。下面这段代码把回溯过程显式写出来适合考试后自查# surv[t][state] (prev_state, input_bit) surv { 1: {0b00: (0b00, 0), 0b10: (0b00, 1)}, 2: {0b00: (0b00, 0), 0b10: (0b00, 1), 0b01: (0b10, 0), 0b11: (0b10, 1)}, 3: {0b00: (0b01, 0), 0b10: (0b01, 1), 0b01: (0b11, 0), 0b11: (0b11, 1)}, 4: {0b00: (0b01, 0), 0b10: (0b01, 1), 0b01: (0b11, 0), 0b11: (0b10, 1)}, } bits [] state 0b11 # 选终态度量最小的状态 for t in range(4, 0, -1): prev, u surv[t][state] bits.append(u) state prev print(bits[::-1]) # [1, 0, 1, 1]代码里的surv字典就是考试卷面画网格图时需要保留的信息每个时刻每个状态只记一条来源和对应的输入比特。回溯时从最后一个时刻往前推得到的比特序列反转一下就是译码结果。4.4 flush bit为什么答案末尾总多出几个 0 或 1很多第六章习题的卷积码编码问“输出序列是什么”答案末尾会多几位这几位就是 flush 产生的。规范做法是信息位后面补记忆深度个 0再继续编码最后丢弃这几位 0 对应的输入只保留输出。上面例子中信息只有 4 位但完整输出是 12 位比4 × 2 8位多了 4 位多出来的就是两个 flush 周期产生的输出。考试时如果只要求编码看清题目有没有说“编码器初始状态为零、末尾需要归零”。如果没提默认也要做因为不做 flush 的话译码端无法确定最终状态维特比回溯就没有合法的终止节点。做题时在编码过程的最后补两个 0能避免丢掉最后两个信息比特的编码输出。5. 对答案之外三个能自查的硬技巧5.1 最小码距 d_min 用暴力枚举兜底题目给一个未知生成矩阵让你求 d_min 并判断纠错能力最稳妥的办法是对所有非零信息向量编码统计码字最小重量。def min_distance(G): k, n len(G), len(G[0]) d n for mask in range(1, 1 k): c [0] * n for i in range(k): if (mask i) 1: c [c[j] ^ G[i][j] for j in range(n)] d min(d, sum(c)) return d G [ [1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1], ] print(min_distance(G)) # 3线性分组码的最小距离等于非零码字的最小重量所以枚举后直接取最小汉明重量即可。这个办法对 (7,4) 这种小参数码非常快在考场上也适合用来验证自己通过 H 列相关性推断出的 d_min 是否正确。5.2 译码结果用编码器回读一遍维特比译码完成后把译出的比特序列送进编码器重新编码比对输出与接收序列的汉明距离应该正好等于幸存路径的最终度量。如果对不上八成是回溯方向反了或者终态选错。这个回读检查同样适用于线性分组码纠正后的码字乘 H^T 必须得到全零向量否则说明错误位置定位错了。5.3 多项式余式为零的快速验证循环码题目做到最后一步“验证码字合法”直接用gf2_poly_mod对完整码字求余余数为零就收工。这里有个小技巧不要把校验位拼回去之后又重新手算一遍长除而是用编码时的中间结果——编码时已经算过code (info (n-k)) | rem整除性是构造时就保证的接收端想验证的是另一件事即收到的序列去掉尾部的校验位后重新编码得到的结果是否和收到的校验位一致或者直接对完整接收序列求余。两种做法等价选计算量小的一种即可。对接收序列求余时如果余数不为零再回头看看是不是信号里把x^n 1的因子弄混了常见的坑是把g(x)的次数当成n-k1导致补位差一位。本文还有配套的精品资源点击获取