1. 先弄清楚Spinal码在解决什么问题以及哈希函数为什么是核心1.1 无速率编码的发到够了为止到底怎么实现在我自己动手用MATLAB复现Spinal码之前对这种无速率编码的理解一直停留在名字很酷的阶段。传统LDPC或者Turbo码需要先假设一个信道信噪比然后确定码率例如1/2、2/3。一旦真实信道比预想的差解码失败就得靠重传比预想的好又会浪费大量冗余。Spinal码的做法完全不同发送端可以不断生成编码符号接收端拿到足够多符号后给个反馈够了 发送端就停止。它不需要提前知道码率也不需要拟合信道模型。这个发到够了为止是如何落地的核心就是把消息切分成若干段之后通过一串哈希状态把整条消息拧成一条状态链再基于每个状态放出一个或多个编码符号。每放出一个符号都是在给这条状态链增加信息冗余。接收端收到足够多的符号后能逐步搜索出最有可能的那条消息路径。因为符号可以无限产生所以理论上这个码是真正无速率的。在我实际用MATLAB实现的时候最有意思的地方不是那些高深的理论推导而是状态哈希这一步。Spinal码的整个纠错能力几乎都压在从上一个状态和当前消息段生成下一个状态这件事上。如果这个函数写得不够好后面再复杂的解码算法也白搭。1.2 One-at-a-Time哈希不是随便选一个而是性能和扩散性的平衡点Spinal码中哈希函数有两个关键用处一是状态更新也就是把前一个状态和当前消息段拼在一起哈希成新的状态二是符号生成从某个状态出发配合计数器不断生成不同编码符号。这两处都需要同一个特性输入哪怕只有一点不同输出也要看起来完全不一样。专业一点叫扩散性。很多人会下意识想到SHA-2或者MD5但稍微算一下复杂度就发现不合适。编码器要为每个消息段至少做一次状态哈希每发送一个符号又要做一次哈希如果哈希函数要处理几百个字节的分组整体吞吐率会急剧下降。One-at-a-Time是我实测下来非常契合的一种查表式哈希每次更新只涉及加减、左移、右移、异或循环体内五六条指令就能完成一个字节的处理而且扩散效果非常不错。它的名字看起来很随意但设计其实很讲究。算法思路大致是对每个字节累加不断做hash加左移10位、hash异或右移6位最后再来一轮移位混洗。因为每一步都同时涉及高位移到低位和低位移到高位加上位异或的非线性最终结果能够把输入比特的微小差异迅速扩散到整个输出空间。我在验证时发现随机改一个消息字节状态输出大约有接近一半的比特位翻转。这直接决定了错误路径在解码时会产生明显偏大的度量让beam搜索更容易保住正确路径。可以说选对哈希函数Spinal码才真正“转”得起来。2. 编码端的MATLAB实现消息分段、状态链与符号生成2.1 消息分段和参数设计设计Spinal码实现的时候第一步就是确定参数。MATLAB里做仿真为了跑得快我通常把参数固定成下面这几个k每个消息段比特数。为了便于按字节哈希我选用k8这样每一段就是一个uint8。nseg消息段数。如果原始消息是msgBytes字节那么nseg length(msgBytes)。v状态位数。我默认v32刚好一个uint32。状态位数太少容易出现不同路径哈希碰撞太多又增加计算和存储开销。symbolBits每个编码符号的比特数。一般取2或者4配合后面的星座映射。spinePerState每个状态产生多少个符号。发送端在状态s_i上要放spinePerState个符号解码端就能根据同一状态生成同样符号去和接收信号对比。消息构造可以直接用randi生成随机字节数组msgBytes randi([0 255], 1, 32); % 32字节消息即 nseg32然后把msgBytes转成uint8避免后面出现类型不一致的问题。每个消息段就对应一棵解码树的一个分支。你也可以选择k16或k24但分支数会爆炸性增长。最常用的还是8位一段这样解码阶段每个节点最多扩展256个子节点配合beam剪枝后MATLAB还能跑得动。2.2 One-at-a-Time哈希函数的MATLAB实现MATLAB的位运算没有C语言那么随意其中一个坑就是默认数据类型是double做bitshift时必须先把变量强制转换成整数类型否则结果会变得很奇怪。另一个坑是MATLAB的bitxor对输入有严格类型要求两边都必须是相同整数类型。这里我给出一个经过实际测试能正常运行的实现function hOut oaatUpdate(h, byteVal) h uint32(h); b uint32(byteVal); h h b; h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); hOut h; end不过Spinal码的状态哈希不是这么简单它需要把上一个32位状态和当前消息段的8位组合起来作为哈希输入。为了保留One-at-a-Time“按字节处理”的特征我先将32位状态拆成4个字节再与当前消息段组成一个5字节数组随后逐字节执行上面那种更新逻辑function hash stateHash(prevState, msgByte) prevState uint32(prevState); bytes uint8([... bitand(bitshift(prevState, -24), 255), ... bitand(bitshift(prevState, -16), 255), ... bitand(bitshift(prevState, -8), 255), ... bitand(prevState, 255), ... msgByte]); h uint32(0); for i 1:5 h h uint32(bytes(i)); h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); end h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); hash h; end如果你希望状态位数是16可以在返回前加一行hash bitand(hash, 65535);但是我不建议在调试初期这么干因为状态截断导致的碰撞会很难排查。先用32位把链路跑通再回来做状态位数的对比实验会轻松很多。2.3 从状态到信道符号伪随机符号流有了状态链之后编码符号的生成方式有很多种。Spinal码的原始设计里符号生成是对当前状态不断应用一个伪随机函数以产生无限制的输出。我这里用One-at-a-Time哈希来充当这个伪随机生成器将当前状态和计数器共同作为输入哈希后取低symbolBits位再映射成实数。function sym genSymbol(state, counter, symbolBits) state uint32(state); counter uint32(counter); bytes uint8([... bitand(bitshift(state, -24), 255), ... bitand(bitshift(state, -16), 255), ... bitand(bitshift(state, -8), 255), ... bitand(state, 255), ... bitand(bitshift(counter, -24), 255), ... bitand(bitshift(counter, -16), 255), ... bitand(bitshift(counter, -8), 255), ... bitand(counter, 255)]); h uint32(0); for i 1:8 h h uint32(bytes(i)); h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); end h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); code bitand(h, 2^symbolBits - 1); sym (double(code) - (2^(symbolBits-1) - 0.5)) / (2^(symbolBits-1)); end上面的sym输出被映射到[-1, 1]区间。symbolBits2时会产生类似4个均匀分布的实数点symbolBits4时产生16个点。我习惯把symbolBits设成2一方面是接收符号的欧氏距离度量更直观另一方面是每个状态产生的符号串长度够大解码端的度量区分度会更好。编码器的主体就是先把所有消息段跑一遍状态链再把每个状态对应的符号拼到一块nseg length(msgBytes); states zeros(1, nseg 1, uint32); states(1) uint32(0); for i 1:nseg states(i 1) stateHash(states(i), msgBytes(i)); end tx []; for i 1:nseg for c 0:spinePerState - 1 tx [tx, genSymbol(states(i 1), c, symbolBits)]; end end发送端把tx送给AWGN信道接收端得到rx tx noise。整个编码过程到这儿就完整了。看起来是不是挺短但它已经实现了无限符号流的本质——只要把counter继续往上增加就能不断给出新符号。3. 解码端怎么找回来倒码树与beam搜索实现3.1 解码为什么可以看成树搜索Spinal码的解码和卷积码的维特比译码有点神似但又不太一样。发送端的状态链是根状态 - 状态1 - 状态2 - ... - 状态nseg每一步的输入是一个未知的消息段。接收端已经拿到了所有发送符号但是不知道每个状态是什么一个自然的思路就是从根状态出发遍历所有可能的消息段组合看哪条路径生成的符号与实际接收符号最像。把所有可能的消息段序列画出来就是一棵巨大的树。第一层有2^k个子节点第二层每个子节点再分2^k个孙节点。直接全部展开是不可能的所以必须做剪枝。Spinal码论文里用的是beam搜索每层只保留累计度量最小的若干条路径其他全部丢弃。这是一个典型的贪心剪枝但配合好的哈希扩散性实际效果已经足够好。3.2 分支度量和beam剪枝的代码框架解码时每个节点需要记录三样东西该节点最新的状态、从根到该节点的累计分值、已经解码出来的消息段序列。在一次完整的编码中如果每个状态生成了spinePerState个符号那么从第i层状态开始解码端也必须生成同样的符号块然后和接收序列中对应位置的符号求欧氏距离平方。实际操作时我先把接收序列rx按状态位置切成块第i层的第j个符号对应接收向量下标(i-1)*spinePerState j。例如spinePerState4时第1层用到的是rx(1:4)第2层用rx(5:8)。这个规则在编码和解码两端必须完全一致否则依次错位解码性能直接崩掉。beam搜索的框架大致是function decoded spineDecode(rx, nseg, beamWidth, spinePerState, symbolBits) beamStates uint32(0); beamScores 0; beams cellstr(char(zeros(beamWidth, 0))); % 或者用 cell 存历史实际操作中用MATLAB结构体数组更直观。每个beam是一个结构体b.state uint32(0); b.score 0; b.path zeros(1, 0); beamList(1) b;然后逐层扩展。每一层先把 beamList 中每个节点当成父节点枚举所有可能的msgValue用stateHash(parentState, msgValue)得到子状态接着根据子状态生成spinePerState个符号与接收信号对应位置求距离新路径的分数等于父节点分数加这一段距离。把所有扩出来的子节点收集到一起按分数升序排序只保留前beamWidth个作为下一层的 beamList。3.3 实际跑通解码的完整代码段为了不绕弯我直接贴一段能跑起来的核心循环function decodedMsg spineDecode(rx, nseg, beamWidth, spinePerState, symbolBits) freq spinePerState; beamStates uint32(0); beamScores 0; beamPaths cell(1, beamWidth); beamPaths{1} uint8([]); for layer 1:nseg candidatesStates uint32([]); candidatesScores []; candidatesPaths {}; for bIdx 1:size(beamStates, 2) parentState beamStates(bIdx); parentScore beamScores(bIdx); parentPath beamPaths{bIdx}; possibleMsgs 0:255; % k8 for msg possibleMsgs childState stateHash(parentState, uint8(msg)); blockStart (layer - 1) * freq 1; blockEnd blockStart freq - 1; rxBlock rx(blockStart:blockEnd); txBlock zeros(1, freq); for cIdx 0:freq - 1 txBlock(cIdx 1) genSymbol(childState, cIdx, symbolBits); end dist sum((rxBlock - txBlock).^2); newScore parentScore dist; newPath [parentPath, uint8(msg)]; candidatesStates(end 1) childState; candidatesScores(end 1) newScore; candidatesPaths{end 1} newPath; end end [~, sortIdx] sort(candidatesScores); keepIdx sortIdx(1:min(beamWidth, length(sortIdx))); beamStates candidatesStates(keepIdx); beamScores candidatesScores(keepIdx); beamPaths candidatesPaths(keepIdx); end [~, bestIdx] min(beamScores); decodedMsg beamPaths{bestIdx}; end注意这段代码用到了cell来保存路径避免了MATLAB在创建二维数组时因为长度不一致而报错。如果消息长度固定且不是太长也可以预先分配矩阵但我觉得在调试阶段使用cell反而省心。这个循环跑完之后decodedMsg就是一组uint8直接和原始msgBytes比较就能得到误码率。3.4 解码结束的判决和反馈模拟实际通信里接收端要判断是否解码成功一种简单方式是发送端对消息做一个循环冗余校验或者直接在消息尾部添加校验段。解码端在最终最佳路径上检查校验信息如果校验通过就发反馈停止。我的仿真里为了直观先固定发送符号数量解码后再计算误码率。这样可以研究“接收符号总数”和“误码率”之间的关系越接近更真实的无速率反馈机制。4. 参数与哈希函数实测那些坑比算法本身更影响效果4.1 状态位数不足会直接带来碰撞错误我最初为了节省内存试过把状态位数设为16位也就是每次stateHash返回后取低16位。结果在消息长度为10字节以上、信噪比稍低时错误路径经常出现和正确路径相同状态的情况。这种状态碰撞一旦发生解码器看到的两个不同消息段会哈希到同一个状态产生完全相同的符号序列度量也会一样剪枝根本没法定夺最终导致路径分裂成两条同样可能的支路误码率居高不下。改用32位状态后碰撞概率显著下降。这里一个简单的计算32位状态空间约42亿beam宽度取16搜索深度取32层在搜过的路径集合里碰撞概率依然非常小。所以我的结论是v32是起步配置不要再低。如果担心64位在MATLAB里不友好用32位足够支撑多数大学级别的仿真实验。4.2 beam宽度不是越大越好beam宽度的实验结果很有意思。当beamWidth4的时候高信噪比场景还能跑但信噪比降低到0dB左右误码率明显抬升原因是剪枝太快正确的路径在早期由于噪声产生的度量偏大被丢弃了。把beamWidth从4提到16性能提升非常明显误码率能下降好几个数量级。再提到64性能增益就很小了但解码时间几乎线性增加因为每层要扩展的候选节点从beamWidth * 256变成64 * 256排序开销也随之增加。我在仿真里一般把beamWidth固定在16。如果你的消息段数超过50为了保证搜索稳定性可以试到32。我的建议是先用16跑通再根据误码率需求往上加不要一上来就追求64。4.3 换一个蹩脚哈希会怎样One-at-a-Time对比测试为了验证One-at-a-Time的价值我做了一组不太严格但很直观的对比。把状态哈希换成一个简单得多的“乘加取模”哈希例如hash bitand(prevState * 31 uint32(msgByte), 4294967295);这就完全抛弃了非线性移位和异或。试验结果非常有趣在高信噪比时两种哈希都能工作因为接收符号足够可靠即使路径度量差距不大也能靠累计分数找回正确路径。但中等信噪比下简单乘加哈希的误码率已经出现平台期而One-at-a-Time还能继续下降。问题出在简单乘法缺乏足够的扩散能力两个不同的(prevState, msgByte)组合很容易算出接近的哈希值生成的符号序列也接近导致解码器难以区分错误路径。这个对比强烈说明了一个原则Spinal码的哈希不是“能算就行”它必须保证输入的任何一位翻转都能以近似50%的概率影响输出每一位。One-at-a-Time在这一点上经过了充分验证而且实现成本很低非常适合MATLAB快速原型验证。4.4 MATLAB特有类型转换和位运算坑最后必须单独列一节MATLAB的坑因为这些坑足够让新手卡上一整天。第一个坑是关于整数溢出的。MATLAB只对uint32或uint64进行自动溢出回卷但如果你用的是普通双精度矩阵bitshift可能会返回不期望的浮点值。所以我所有的哈希元素都强制uint32并且在函数入口写uint32(...)转一次避免从外部传入double。第二个坑是bitxor对输入类型的要求比较严格。它要求两个输入都是整数类型且长度相同。我写代码的一律换成bitxor(h, bitshift(h, -6))而不是使用uint64和uint32混用。如果你真的需要64位状态最好的办法是自己用两个uint32拼接避免MATLAB的64位位运算性能低下。第三个坑是bitshift(h, -6)这种写法。MATLAB的bitshift支持负数移位表示右移这一点和C语言不同。初学的时候很容易写成bitshift(h, 6)忘记负号导致扩散性完全失效且输出全是低位的混乱。我的经验是把One-at-a-Time的公式用bitshift照搬时仔细对齐每个正负号再做一个简单的汉明距离测试确认输出足够扩散然后再往下走。最后还有一个效率坑在解码循环里频繁调用genSymbol会产生大量函数调用开销导致仿真很慢。一个可行的优化是在状态哈希之后把每个状态在spinePerState个计数器下对应的符号值预先生成好存成一个矩阵解码时直接查表。我实测过这种方式能让整个仿真提速三到五倍尤其在消息段数和beam宽度都比较大时。5. 扩展思路与个人收尾这套MATLAB框架跑通之后可以向几个方向扩展。一是增加反馈机制模拟。让发送端先发送少量符号接收端解码并检查校验如果失败就继续追加符号直到成功或达到最大符号数。这个过程可以画出一条“发送符号数—误帧率”的曲线非常直观地验证无速率特性。二是把符号星座从PAM扩展到QPSK或16QAM。genSymbol返回的是实数改成二维复数符号后只需要把距离度量改为复数的模方距离sum(abs(rxBlock - txBlock).^2)其他部分基本不用动。三是优化解码性能。当前beam搜索每层对所有候选排序当beamWidth和k变大时排序会成为瓶颈。可以把排序改成部分选择或者直接对得分做分段截断。不过对MATLAB原型验证来说现有方案已经够清晰不需要过度优化。最后分享一下我的个人习惯。每次改完哈希函数或者参数我不会直接看误码率而是先跑一个固定状态的“可复现测试”用固定随机种子生成消息固定信噪比固定噪声序列然后确认编码解码完全一致。只有在确定性测试通过后我才会切换到随机信噪比和随机消息统计平均性能。这种“先确定性再随机性”的做法救了我无数次因为类型转换或移位方向导致的隐性错误。Spinal码最大的魅力在于它用最简单的哈希加树搜索就实现了接近香农限的性能。而One-at-a-Time哈希在其中扮演的角色比很多人想象中更重要。如果你打算在MATLAB里自己写一遍我强烈建议从这一版开始先把状态链和beam搜索跑通再去碰那些更花哨的优化。你会发现代码不长但每个参数背后都藏着足够的细节等着你去踩。 
长河君 · 2026/10/20 18:06:02 · 阅读 1.2k 用MATLAB实现Spinal码：无速率编码与哈希函数实践
1. 先弄清楚Spinal码在解决什么问题以及哈希函数为什么是核心1.1 无速率编码的发到够了为止到底怎么实现在我自己动手用MATLAB复现Spinal码之前对这种无速率编码的理解一直停留在名字很酷的阶段。传统LDPC或者Turbo码需要先假设一个信道信噪比然后确定码率例如1/2、2/3。一旦真实信道比预想的差解码失败就得靠重传比预想的好又会浪费大量冗余。Spinal码的做法完全不同发送端可以不断生成编码符号接收端拿到足够多符号后给个反馈够了 发送端就停止。它不需要提前知道码率也不需要拟合信道模型。这个发到够了为止是如何落地的核心就是把消息切分成若干段之后通过一串哈希状态把整条消息拧成一条状态链再基于每个状态放出一个或多个编码符号。每放出一个符号都是在给这条状态链增加信息冗余。接收端收到足够多的符号后能逐步搜索出最有可能的那条消息路径。因为符号可以无限产生所以理论上这个码是真正无速率的。在我实际用MATLAB实现的时候最有意思的地方不是那些高深的理论推导而是状态哈希这一步。Spinal码的整个纠错能力几乎都压在从上一个状态和当前消息段生成下一个状态这件事上。如果这个函数写得不够好后面再复杂的解码算法也白搭。1.2 One-at-a-Time哈希不是随便选一个而是性能和扩散性的平衡点Spinal码中哈希函数有两个关键用处一是状态更新也就是把前一个状态和当前消息段拼在一起哈希成新的状态二是符号生成从某个状态出发配合计数器不断生成不同编码符号。这两处都需要同一个特性输入哪怕只有一点不同输出也要看起来完全不一样。专业一点叫扩散性。很多人会下意识想到SHA-2或者MD5但稍微算一下复杂度就发现不合适。编码器要为每个消息段至少做一次状态哈希每发送一个符号又要做一次哈希如果哈希函数要处理几百个字节的分组整体吞吐率会急剧下降。One-at-a-Time是我实测下来非常契合的一种查表式哈希每次更新只涉及加减、左移、右移、异或循环体内五六条指令就能完成一个字节的处理而且扩散效果非常不错。它的名字看起来很随意但设计其实很讲究。算法思路大致是对每个字节累加不断做hash加左移10位、hash异或右移6位最后再来一轮移位混洗。因为每一步都同时涉及高位移到低位和低位移到高位加上位异或的非线性最终结果能够把输入比特的微小差异迅速扩散到整个输出空间。我在验证时发现随机改一个消息字节状态输出大约有接近一半的比特位翻转。这直接决定了错误路径在解码时会产生明显偏大的度量让beam搜索更容易保住正确路径。可以说选对哈希函数Spinal码才真正“转”得起来。2. 编码端的MATLAB实现消息分段、状态链与符号生成2.1 消息分段和参数设计设计Spinal码实现的时候第一步就是确定参数。MATLAB里做仿真为了跑得快我通常把参数固定成下面这几个k每个消息段比特数。为了便于按字节哈希我选用k8这样每一段就是一个uint8。nseg消息段数。如果原始消息是msgBytes字节那么nseg length(msgBytes)。v状态位数。我默认v32刚好一个uint32。状态位数太少容易出现不同路径哈希碰撞太多又增加计算和存储开销。symbolBits每个编码符号的比特数。一般取2或者4配合后面的星座映射。spinePerState每个状态产生多少个符号。发送端在状态s_i上要放spinePerState个符号解码端就能根据同一状态生成同样符号去和接收信号对比。消息构造可以直接用randi生成随机字节数组msgBytes randi([0 255], 1, 32); % 32字节消息即 nseg32然后把msgBytes转成uint8避免后面出现类型不一致的问题。每个消息段就对应一棵解码树的一个分支。你也可以选择k16或k24但分支数会爆炸性增长。最常用的还是8位一段这样解码阶段每个节点最多扩展256个子节点配合beam剪枝后MATLAB还能跑得动。2.2 One-at-a-Time哈希函数的MATLAB实现MATLAB的位运算没有C语言那么随意其中一个坑就是默认数据类型是double做bitshift时必须先把变量强制转换成整数类型否则结果会变得很奇怪。另一个坑是MATLAB的bitxor对输入有严格类型要求两边都必须是相同整数类型。这里我给出一个经过实际测试能正常运行的实现function hOut oaatUpdate(h, byteVal) h uint32(h); b uint32(byteVal); h h b; h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); hOut h; end不过Spinal码的状态哈希不是这么简单它需要把上一个32位状态和当前消息段的8位组合起来作为哈希输入。为了保留One-at-a-Time“按字节处理”的特征我先将32位状态拆成4个字节再与当前消息段组成一个5字节数组随后逐字节执行上面那种更新逻辑function hash stateHash(prevState, msgByte) prevState uint32(prevState); bytes uint8([... bitand(bitshift(prevState, -24), 255), ... bitand(bitshift(prevState, -16), 255), ... bitand(bitshift(prevState, -8), 255), ... bitand(prevState, 255), ... msgByte]); h uint32(0); for i 1:5 h h uint32(bytes(i)); h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); end h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); hash h; end如果你希望状态位数是16可以在返回前加一行hash bitand(hash, 65535);但是我不建议在调试初期这么干因为状态截断导致的碰撞会很难排查。先用32位把链路跑通再回来做状态位数的对比实验会轻松很多。2.3 从状态到信道符号伪随机符号流有了状态链之后编码符号的生成方式有很多种。Spinal码的原始设计里符号生成是对当前状态不断应用一个伪随机函数以产生无限制的输出。我这里用One-at-a-Time哈希来充当这个伪随机生成器将当前状态和计数器共同作为输入哈希后取低symbolBits位再映射成实数。function sym genSymbol(state, counter, symbolBits) state uint32(state); counter uint32(counter); bytes uint8([... bitand(bitshift(state, -24), 255), ... bitand(bitshift(state, -16), 255), ... bitand(bitshift(state, -8), 255), ... bitand(state, 255), ... bitand(bitshift(counter, -24), 255), ... bitand(bitshift(counter, -16), 255), ... bitand(bitshift(counter, -8), 255), ... bitand(counter, 255)]); h uint32(0); for i 1:8 h h uint32(bytes(i)); h h bitshift(h, 10); h bitxor(h, bitshift(h, -6)); end h h bitshift(h, 3); h bitxor(h, bitshift(h, -11)); h h bitshift(h, 15); code bitand(h, 2^symbolBits - 1); sym (double(code) - (2^(symbolBits-1) - 0.5)) / (2^(symbolBits-1)); end上面的sym输出被映射到[-1, 1]区间。symbolBits2时会产生类似4个均匀分布的实数点symbolBits4时产生16个点。我习惯把symbolBits设成2一方面是接收符号的欧氏距离度量更直观另一方面是每个状态产生的符号串长度够大解码端的度量区分度会更好。编码器的主体就是先把所有消息段跑一遍状态链再把每个状态对应的符号拼到一块nseg length(msgBytes); states zeros(1, nseg 1, uint32); states(1) uint32(0); for i 1:nseg states(i 1) stateHash(states(i), msgBytes(i)); end tx []; for i 1:nseg for c 0:spinePerState - 1 tx [tx, genSymbol(states(i 1), c, symbolBits)]; end end发送端把tx送给AWGN信道接收端得到rx tx noise。整个编码过程到这儿就完整了。看起来是不是挺短但它已经实现了无限符号流的本质——只要把counter继续往上增加就能不断给出新符号。3. 解码端怎么找回来倒码树与beam搜索实现3.1 解码为什么可以看成树搜索Spinal码的解码和卷积码的维特比译码有点神似但又不太一样。发送端的状态链是根状态 - 状态1 - 状态2 - ... - 状态nseg每一步的输入是一个未知的消息段。接收端已经拿到了所有发送符号但是不知道每个状态是什么一个自然的思路就是从根状态出发遍历所有可能的消息段组合看哪条路径生成的符号与实际接收符号最像。把所有可能的消息段序列画出来就是一棵巨大的树。第一层有2^k个子节点第二层每个子节点再分2^k个孙节点。直接全部展开是不可能的所以必须做剪枝。Spinal码论文里用的是beam搜索每层只保留累计度量最小的若干条路径其他全部丢弃。这是一个典型的贪心剪枝但配合好的哈希扩散性实际效果已经足够好。3.2 分支度量和beam剪枝的代码框架解码时每个节点需要记录三样东西该节点最新的状态、从根到该节点的累计分值、已经解码出来的消息段序列。在一次完整的编码中如果每个状态生成了spinePerState个符号那么从第i层状态开始解码端也必须生成同样的符号块然后和接收序列中对应位置的符号求欧氏距离平方。实际操作时我先把接收序列rx按状态位置切成块第i层的第j个符号对应接收向量下标(i-1)*spinePerState j。例如spinePerState4时第1层用到的是rx(1:4)第2层用rx(5:8)。这个规则在编码和解码两端必须完全一致否则依次错位解码性能直接崩掉。beam搜索的框架大致是function decoded spineDecode(rx, nseg, beamWidth, spinePerState, symbolBits) beamStates uint32(0); beamScores 0; beams cellstr(char(zeros(beamWidth, 0))); % 或者用 cell 存历史实际操作中用MATLAB结构体数组更直观。每个beam是一个结构体b.state uint32(0); b.score 0; b.path zeros(1, 0); beamList(1) b;然后逐层扩展。每一层先把 beamList 中每个节点当成父节点枚举所有可能的msgValue用stateHash(parentState, msgValue)得到子状态接着根据子状态生成spinePerState个符号与接收信号对应位置求距离新路径的分数等于父节点分数加这一段距离。把所有扩出来的子节点收集到一起按分数升序排序只保留前beamWidth个作为下一层的 beamList。3.3 实际跑通解码的完整代码段为了不绕弯我直接贴一段能跑起来的核心循环function decodedMsg spineDecode(rx, nseg, beamWidth, spinePerState, symbolBits) freq spinePerState; beamStates uint32(0); beamScores 0; beamPaths cell(1, beamWidth); beamPaths{1} uint8([]); for layer 1:nseg candidatesStates uint32([]); candidatesScores []; candidatesPaths {}; for bIdx 1:size(beamStates, 2) parentState beamStates(bIdx); parentScore beamScores(bIdx); parentPath beamPaths{bIdx}; possibleMsgs 0:255; % k8 for msg possibleMsgs childState stateHash(parentState, uint8(msg)); blockStart (layer - 1) * freq 1; blockEnd blockStart freq - 1; rxBlock rx(blockStart:blockEnd); txBlock zeros(1, freq); for cIdx 0:freq - 1 txBlock(cIdx 1) genSymbol(childState, cIdx, symbolBits); end dist sum((rxBlock - txBlock).^2); newScore parentScore dist; newPath [parentPath, uint8(msg)]; candidatesStates(end 1) childState; candidatesScores(end 1) newScore; candidatesPaths{end 1} newPath; end end [~, sortIdx] sort(candidatesScores); keepIdx sortIdx(1:min(beamWidth, length(sortIdx))); beamStates candidatesStates(keepIdx); beamScores candidatesScores(keepIdx); beamPaths candidatesPaths(keepIdx); end [~, bestIdx] min(beamScores); decodedMsg beamPaths{bestIdx}; end注意这段代码用到了cell来保存路径避免了MATLAB在创建二维数组时因为长度不一致而报错。如果消息长度固定且不是太长也可以预先分配矩阵但我觉得在调试阶段使用cell反而省心。这个循环跑完之后decodedMsg就是一组uint8直接和原始msgBytes比较就能得到误码率。3.4 解码结束的判决和反馈模拟实际通信里接收端要判断是否解码成功一种简单方式是发送端对消息做一个循环冗余校验或者直接在消息尾部添加校验段。解码端在最终最佳路径上检查校验信息如果校验通过就发反馈停止。我的仿真里为了直观先固定发送符号数量解码后再计算误码率。这样可以研究“接收符号总数”和“误码率”之间的关系越接近更真实的无速率反馈机制。4. 参数与哈希函数实测那些坑比算法本身更影响效果4.1 状态位数不足会直接带来碰撞错误我最初为了节省内存试过把状态位数设为16位也就是每次stateHash返回后取低16位。结果在消息长度为10字节以上、信噪比稍低时错误路径经常出现和正确路径相同状态的情况。这种状态碰撞一旦发生解码器看到的两个不同消息段会哈希到同一个状态产生完全相同的符号序列度量也会一样剪枝根本没法定夺最终导致路径分裂成两条同样可能的支路误码率居高不下。改用32位状态后碰撞概率显著下降。这里一个简单的计算32位状态空间约42亿beam宽度取16搜索深度取32层在搜过的路径集合里碰撞概率依然非常小。所以我的结论是v32是起步配置不要再低。如果担心64位在MATLAB里不友好用32位足够支撑多数大学级别的仿真实验。4.2 beam宽度不是越大越好beam宽度的实验结果很有意思。当beamWidth4的时候高信噪比场景还能跑但信噪比降低到0dB左右误码率明显抬升原因是剪枝太快正确的路径在早期由于噪声产生的度量偏大被丢弃了。把beamWidth从4提到16性能提升非常明显误码率能下降好几个数量级。再提到64性能增益就很小了但解码时间几乎线性增加因为每层要扩展的候选节点从beamWidth * 256变成64 * 256排序开销也随之增加。我在仿真里一般把beamWidth固定在16。如果你的消息段数超过50为了保证搜索稳定性可以试到32。我的建议是先用16跑通再根据误码率需求往上加不要一上来就追求64。4.3 换一个蹩脚哈希会怎样One-at-a-Time对比测试为了验证One-at-a-Time的价值我做了一组不太严格但很直观的对比。把状态哈希换成一个简单得多的“乘加取模”哈希例如hash bitand(prevState * 31 uint32(msgByte), 4294967295);这就完全抛弃了非线性移位和异或。试验结果非常有趣在高信噪比时两种哈希都能工作因为接收符号足够可靠即使路径度量差距不大也能靠累计分数找回正确路径。但中等信噪比下简单乘加哈希的误码率已经出现平台期而One-at-a-Time还能继续下降。问题出在简单乘法缺乏足够的扩散能力两个不同的(prevState, msgByte)组合很容易算出接近的哈希值生成的符号序列也接近导致解码器难以区分错误路径。这个对比强烈说明了一个原则Spinal码的哈希不是“能算就行”它必须保证输入的任何一位翻转都能以近似50%的概率影响输出每一位。One-at-a-Time在这一点上经过了充分验证而且实现成本很低非常适合MATLAB快速原型验证。4.4 MATLAB特有类型转换和位运算坑最后必须单独列一节MATLAB的坑因为这些坑足够让新手卡上一整天。第一个坑是关于整数溢出的。MATLAB只对uint32或uint64进行自动溢出回卷但如果你用的是普通双精度矩阵bitshift可能会返回不期望的浮点值。所以我所有的哈希元素都强制uint32并且在函数入口写uint32(...)转一次避免从外部传入double。第二个坑是bitxor对输入类型的要求比较严格。它要求两个输入都是整数类型且长度相同。我写代码的一律换成bitxor(h, bitshift(h, -6))而不是使用uint64和uint32混用。如果你真的需要64位状态最好的办法是自己用两个uint32拼接避免MATLAB的64位位运算性能低下。第三个坑是bitshift(h, -6)这种写法。MATLAB的bitshift支持负数移位表示右移这一点和C语言不同。初学的时候很容易写成bitshift(h, 6)忘记负号导致扩散性完全失效且输出全是低位的混乱。我的经验是把One-at-a-Time的公式用bitshift照搬时仔细对齐每个正负号再做一个简单的汉明距离测试确认输出足够扩散然后再往下走。最后还有一个效率坑在解码循环里频繁调用genSymbol会产生大量函数调用开销导致仿真很慢。一个可行的优化是在状态哈希之后把每个状态在spinePerState个计数器下对应的符号值预先生成好存成一个矩阵解码时直接查表。我实测过这种方式能让整个仿真提速三到五倍尤其在消息段数和beam宽度都比较大时。5. 扩展思路与个人收尾这套MATLAB框架跑通之后可以向几个方向扩展。一是增加反馈机制模拟。让发送端先发送少量符号接收端解码并检查校验如果失败就继续追加符号直到成功或达到最大符号数。这个过程可以画出一条“发送符号数—误帧率”的曲线非常直观地验证无速率特性。二是把符号星座从PAM扩展到QPSK或16QAM。genSymbol返回的是实数改成二维复数符号后只需要把距离度量改为复数的模方距离sum(abs(rxBlock - txBlock).^2)其他部分基本不用动。三是优化解码性能。当前beam搜索每层对所有候选排序当beamWidth和k变大时排序会成为瓶颈。可以把排序改成部分选择或者直接对得分做分段截断。不过对MATLAB原型验证来说现有方案已经够清晰不需要过度优化。最后分享一下我的个人习惯。每次改完哈希函数或者参数我不会直接看误码率而是先跑一个固定状态的“可复现测试”用固定随机种子生成消息固定信噪比固定噪声序列然后确认编码解码完全一致。只有在确定性测试通过后我才会切换到随机信噪比和随机消息统计平均性能。这种“先确定性再随机性”的做法救了我无数次因为类型转换或移位方向导致的隐性错误。Spinal码最大的魅力在于它用最简单的哈希加树搜索就实现了接近香农限的性能。而One-at-a-Time哈希在其中扮演的角色比很多人想象中更重要。如果你打算在MATLAB里自己写一遍我强烈建议从这一版开始先把状态链和beam搜索跑通再去碰那些更花哨的优化。你会发现代码不长但每个参数背后都藏着足够的细节等着你去踩。