如何防止网站被攻击网站建设 大公司好

当前位置： 首页 > news >正文

如何防止网站被攻击,网站建设 大公司好,响应式网站模板 视差,电子政务公开 网站建设文章目录 二、关键算法原理剖析2.1 Viterbi 解码2.1.1 卷积码与网格图基础卷积码网格图生成多项式理想情况下解码过程 2.1.2 Viterbi 算法核心思想2.1.3 路径度量与状态转移机制2.1.4 算法流程与关键步骤详解2.1.5 译码算法举例与复杂度分析2.1.6 算法代码示例… 文章目录 二、关键算法原理剖析2.1 Viterbi 解码2.1.1 卷积码与网格图基础卷积码网格图生成多项式理想情况下解码过程 2.1.2 Viterbi 算法核心思想2.1.3 路径度量与状态转移机制2.1.4 算法流程与关键步骤详解2.1.5 译码算法举例与复杂度分析2.1.6 算法代码示例 本博客为系列博客主要讲解各基带算法的原理与应用包括viterbi解码、Turbo编解码、Polar编解码、CORDIC算法、CRC校验、FFT/DFT、QAMtiaozhi/解调、QPSK调制/解调。其他博客链接如下 探秘基带算法从原理到5G时代的通信变革【一】引言探秘基带算法从原理到5G时代的通信变革【二】Viterbi解码探秘基带算法从原理到5G时代的通信变革【三】Turbo 编解码探秘基带算法从原理到5G时代的通信变革【四】Polar 编解码一探秘基带算法从原理到5G时代的通信变革【四】Polar 编解码二探秘基带算法从原理到5G时代的通信变革【五】CORDIC算法探秘基带算法从原理到5G时代的通信变革【六】CRC 校验探秘基带算法从原理到5G时代的通信变革【七】FFT/DFT探秘基带算法从原理到5G时代的通信变革【八】QAM 调制 / 解调探秘基带算法从原理到5G时代的通信变革【九】QPSK调制/解调探秘基带算法从原理到5G时代的通信变革【十】基带算法应用与对比 二、关键算法原理剖析 2.1 Viterbi 解码 2.1.1 卷积码与网格图基础 卷积码 在深入探讨 Viterbi 解码算法之前有必要先了解其赖以依存的卷积码和网格图的基本概念。卷积码作为一种重要的纠错编码方式与分组码有所不同它并非将输入数据划分为独立的分组进行编码而是通过将输入数据与编码器的状态进行卷积运算来生成输出码字。这一过程中编码器的状态会随着输入数据的变化而不断更新使得输出码字不仅与当前输入数据相关还与之前的输入数据存在联系从而能够利用历史信息来提高纠错能力。 以一个简单的 (2, 1, 3) 卷积码编码器为例其中 “2” 表示输出码字的位数“1” 表示输入数据的位数“3” 表示约束长度。该编码器由两个移位寄存器和一些逻辑门组成输入数据在时钟信号的驱动下依次进入移位寄存器同时与移位寄存器中的状态进行逻辑运算生成两个输出比特形成输出码字。这种编码方式使得前后码字之间存在着紧密的相关性为后续的解码提供了更多的信息。 在初始时刻假设寄存器状态为000。 在t1时刻输入1则寄存器状态变为100相当于把初始寄存器状态000中从左往右第三个0“挤”掉了。 在t2时刻输入0则寄存器状态变为010相当于把t1时刻寄存器状态100中从左往右第三个0“挤”掉了。 在t3时刻输入1则寄存器状态变为101相当于把t2时刻寄存器状态010中从做往右第三个0“挤”掉了。 接着需要两个冲洗比特连续输入两个0用以清空寄存器。 在t4时刻输入0则寄存器状态从t3时刻的101变为010相当于把t3时刻寄存器状态101中从做往右第三个1“挤”掉了。 在t5时刻输入0则寄存器状态从t4时刻的010变为001相当于把t4时刻寄存器状态010中从做往右第三个0“挤”掉了。 为什么用两个冲洗比特就可以达到清空寄存器的目的呢为什么不是三个呢毕竟再输入一个0寄存器状态才恢复为初始状态000呀。其实输入两个就达到了清空寄存器的目的了试想一下如果在t6时刻输入一个1这时候寄存器状态就从001变为100t5时刻的寄存器状态中的1被“挤”掉了也就是这个1被舍弃掉了。换言之这个1是没用的所以两个冲洗比特足矣只需要把寄存器状态变为00X的形式即可其中X可为0或1。不管X为0还是1都对下一个输入的寄存器状态没有影响。在下一个输入进来的时候X都会被舍弃掉。 图卷积编码过程示意 卷积编码是有限状态机器件。只有有限个状态机制状态提供了有关过去序列过程以及一组将来可能输出序列的限制即下一状态总是受到前一状态的限制。 图有限状态机示意 网格图 为了更直观地展示卷积码码字之间的相关性引入了网格图的概念。网格图是一种按时间顺序排列的状态结点矩阵每一列代表当前时刻的所有可能状态最左侧第一列代表初始状态t 0随着时间的推移从左至右依次表示后续时刻的状态。在网格图中从一个状态到另一个状态的转移用线段表示这些线段被称为分支每个分支都对应着一个输入比特和一个输出码字。 给定输入数据序列根据网格图可以方便的得到编码输出序列。虚线代表输入比特为1实线代表输入比特为0。例如当输入数据序列为1 1 0 1 1时可根据网格图得到其对应的编码输出序列为11 01 01 00 01如下图所示 图(2, 1, 3) 卷积码的网格图 一个nkK卷积编码器由Kk级移位寄存器和n个模2加法器输出发生器组成。编码输出的n比特不仅取决于正在移入的k比特还与这之前输入的K-1个k位有关。所以卷积编码器是有“记忆”的。 图nkK卷积编码器 参考链接卷积码Convolutional Code - 知乎 生成多项式 卷积码是一种重要的信道编码技术其核心原理是通过线性移位寄存器对输入信息序列进行卷积运算生成具有记忆特性的冗余码元。生成多项式是描述卷积码编码规则的核心数学工具通常用一组二进制系数向量表示寄存器抽头连接关系。例如约束长度K3的7,5卷积码其生成多项式可表示为八进制数7,5对应二进制g₁111和g₂101分别代表两组模2加法器的连接方式。每个多项式中的1表示寄存器对应位置参与模2加法运算0则表示断开连接。 在编码过程中信息比特通过移位寄存器逐位输入寄存器状态与生成多项式共同决定输出码字。对于码率R1/2的典型结构每个输入比特会生成两个输出比特 c 1 m j ⊕ m j − 1 ⊕ m j − 2 c₁ mⱼ⊕mⱼ₋₁⊕mⱼ₋₂ c1​mj​⊕mj−1​⊕mj−2​ c 2 m j ⊕ m j − 2 c₂ mⱼ⊕mⱼ₋₂ c2​mj​⊕mj−2​。这种线性组合赋予卷积码连续的关联特性使其纠错能力不仅依赖当前输入还与前面K-1个历史比特相关。约束长度K作为关键参数决定了编码器的记忆深度和状态复杂度通常K值增大会提升纠错性能但同时也增加解码复杂度。 理想情况下解码过程 卷积码的编码过程与网格图中的一条路径对应即接收端接收到的序列的编码过程与网格图中的路径一一对应。当序列长度为K时网格中有2K条不同的路径和编码器的2K种输入序列对应。在网格图中每个状态转移的过程中都会输出编码码字。译码器建立和编码器相同的网格图 据此查询可得到解码码流。 理想状况下假设在传输过程中没有错误发生在接收端根据已经存在的网格图很容易解码得到原始比特流。 以tail-bits卷积码为例假如接收端收到的比特流为’1101010001’, 先按2 bit宽度分组11 01 01 00 01解码过程如下 从t0的初始状态开始tail-bits编码器的初始状态为’00’ 查询输出为11时的转移路径如下图粗线标志此时编码器输入bit为1才能走该转移路径,因此可得到解码的第一bit:1 t1时状态为‘10’根据接收到的第二组‘01’查询从该状态出发的两条转移路径 只有输入为1时才能得到‘01’的输出因此可得到此刻的转移路径把其他无关路径删除。因此解码得到第二比特为1. 以此类推可在网格图上得到完整的状态转移路径及所有解码数据11011. 现实中不会存在这种理想状态信号经过复杂信道后均会引入不同程度错误因此在接收端不会真正使用这种解码算法。 参考链接维特比译码器(Viterbi Decoder)硬件架构(二)–卷积码解码算法_trellis diagram-CSDN博客 2.1.2 Viterbi 算法核心思想 Viterbi 算法是由 Andrew J. Viterbi 在 1967 年提出的是基于卷积码网格图的最大似然译码算法。最大似然译码是把已接收序列与所有可能的发送序列进行比较选出码距最小的序列作为发送序列。对于(n,k,K)卷积码当发送 K 组信息比特时网格图上可能有 2kL 个发送序列译码器需存储并比较这些序列以找到码距最小的序列但当传信率和信息组数 K 较大时译码器难以实现。Viterbi 算法对最大似然解码进行简化不是一次性比较所有可能的路径而是接收一段、计算和比较一段选择有最大似然可能的码段使整个码序列具有最大似然值其译码过程类似动态规划。 几个概念 分支度量BM, Branch Metric是对于网格中每个路径而言表示其对应的输出码字与接收到的码字之间的差距。分支度量计算的是发射和接收内容之间的“距离”它是为网格中的每条分支路径定义的。在硬判决译码中给出一组已经数字化的接收监督比特分支度量就是监督比特预测值和接收监督比特之间的汉明距离。下图展示了一个示例其中接收的位为00对于每个状态转移分支路径上的数字显示该转移的分支度量。其中有两条路径的分支量度为0对应于汉明距离为0的唯一状态和转移关系其他非0分支量度对应于存在位错误的情况。 图分支度量计算 参考链接 Viterbi Decoding of Convolutional Codes 路径度量PMPath Metric是针对网格中每个状态节点对应所有到达该节点所走过的最有可能路径的分支度量值的累计结果。对于硬判决解码“最有可能”是指在计算从初始状态到当前状态之间的所有可能路径度量后取汉明距离最小的那条。具有最小汉明距离的路径使误码最小化并且当误码率较低时具有最大似然度。 Viterbi 算法作为一种基于动态规划的最优路径搜索算法其核心思想是在卷积码对应的网格图中按照时间顺序逐步搜索出一条最优路径这条路径所对应的输入序列即为最有可能的原始信息序列。在搜索过程中算法会根据当前接收到的符号以及状态转移概率计算出到达每个状态的最优路径度量值并保留这些最优路径。维特比算法的关键点在于接收机可以使用分支度量和先前计算的状态路径度量递推地计算当前状态的路径度量。 以通信系统中的信号传输为例假设发送端通过卷积码编码器将原始信息编码后发送出去信号在传输过程中受到噪声干扰接收端接收到的是带有噪声的信号序列。此时Viterbi 算法在网格图中从初始状态开始对于每个时刻的每个状态计算从所有可能的前一状态转移到该状态的路径度量值。路径度量值通常反映了接收序列与假设路径的输出序列之间的差异程度差异越小路径度量值越小。 例如在硬判决译码中常采用汉明距离来计算路径度量值即比较接收序列和假设路径输出序列对应比特位不同的个数在软判决译码中多采用欧几里得距离它考虑了接收信号的幅度等信息能更准确地反映信号之间的差异。在计算出所有可能路径的度量值后算法选择其中最小的度量值对应的路径作为到达该状态的幸存路径也就是当前最优路径并记录下这条路径的相关信息如路径的前一状态等。随着时间的推进算法不断重复上述计算和选择过程直到处理完接收序列的最后一个符号。此时在所有状态中选择具有最小路径度量值的状态作为最终状态然后从该最终状态开始沿着之前记录的幸存路径回溯到初始状态从而得到最有可能的原始信息序列。下图展示了 Viterbi 算法在网格图中搜索最优路径的过程从图中可以看到算法如何在每个时刻选择最优路径最终找到从初始状态到最终状态的最优路径。 图Viterbi 算法在网格图中搜索最优路径 2.1.3 路径度量与状态转移机制 路径度量是 Viterbi 算法中衡量路径优劣的关键指标它定义为路径上所有分支的度量值之和。分支度量值则根据接收符号与预期符号之间的差异来计算在硬判决情况下常使用汉明距离作为分支度量值即两个等长比特序列中对应比特不同的个数。例如接收序列为 1011假设路径的输出序列为 1101那么它们之间的汉明距离为 3因为有 3 个比特位不同。在软判决中由于考虑了信号的幅度等更多信息常采用欧几里得距离作为分支度量值。欧几里得距离是指在多维空间中两个点之间的直线距离在通信中可将接收信号和假设路径输出信号看作多维空间中的点通过计算它们之间的欧几里得距离来衡量差异。 计算路径度量 时刻i的路径度量假设接收机在时刻i已计算好每个状态s的路径量度PM[s,i] 卷积码编码约束度为K时状态数为2K-1。在硬判决译码中PM[s,i]是接收监督比特与最可能发送消息比较得到的差错比特总数常将状态“00”作为起始状态。最可能状态的判断在时刻i的所有可能状态里具有最小路径度量的状态就是最可能的状态。若存在多个具备最小路径度量的状态那么它们成为最可能状态的可能性相等。时刻i1的路径度量确定方法时刻i 1的状态s由时刻i的两种可能状态α和β转移而来α和β仅取决于卷积码的编码约束度与生成多项式无关。比如在下图的例子中状态00对应的α 00β 01状态01对应的α 10β 11 。确定时刻i1下每个状态s的路径度量 P M [ s , i 1 ] PM[s,i 1] PM[s,i1]时要考虑从时刻i的α或β状态转移过来产生的误码情况。例如在下图时刻i1到达状态01存在两种情况 若发射机在时刻i位于状态10且第i个信息比特为0发射机输出监督位11接收比特为00产生2位误码此时新的状态路径度量 P M [ 01 , i 1 ] P M [ 10 , i ] 2 PM[01,i 1]PM[10,i]2 PM[01,i1]PM[10,i]2。若发射机在时刻i位于状态11且第i个信息比特为0发射机输出监督位01接收比特为00产生1位误码此时新的状态路径度量\(PM[01,i 1]PM[11,i]1 \)。总结可得计算路径度量的公式 \(PM[s,i 1] \min(PM[\alpha,i]BM[\alpha \to s],PM[\beta,i]BM[\beta \to s]) \)在译码算法中记录最小汉明距离对应的路径很重要后续要通过跟踪该路径从最终状态遍历到最初状态再将估计比特倒序从而得到最可能的消息。 图分支度量计算 状态转移是指在网格图中从一个状态转移到另一个状态的过程每个状态转移都对应着一个分支度量值。在卷积码的编码过程中状态转移是由输入比特决定的。例如在一个 (2, 1, 3) 卷积码中当前状态为 00若输入比特为 0则状态转移到 00输出码字为 00若输入比特为 1则状态转移到 10输出码字为 11。在 Viterbi 解码过程中当接收到一个符号时需要根据当前状态和所有可能的输入比特计算出从当前状态转移到下一个状态的分支度量值。假设当前状态为 10接收到的符号为 11当输入比特为 0 时从状态 10 转移到状态 01对应的输出码字为 01此时计算接收符号 11 与输出码字 01 的分支度量值当输入比特为 1 时从状态 10 转移到状态 11对应的输出码字为 11再计算接收符号 11 与输出码字 11 的分支度量值。然后将这些分支度量值与之前到达当前状态的路径度量值相加得到到达下一个状态的路径度量值。通过比较不同输入比特对应的路径度量值选择最小的路径度量值对应的路径作为幸存路径更新路径度量和路径历史。这样随着解码过程的推进不断根据状态转移和路径度量的计算来确定最优路径。 2.1.4 算法流程与关键步骤详解 Viterbi 解码算法的流程主要包括初始化、递推、终止和回溯四个关键步骤。 初始化阶段需要确定所有状态在时刻 t 0 的路径度量值。通常将起始状态的路径度量设为 0表示从起始状态出发没有任何差异而对于其他所有状态路径度量则设为无穷大这意味着在初始阶段这些状态是不可能直接到达的只有通过后续的状态转移和路径度量计算才有可能更新这些状态的路径度量值。同时还需要初始化路径历史记录每个状态的前一状态信息以便在回溯阶段能够找到最优路径。 递推阶段是 Viterbi 算法的核心部分在每个时刻 t 和每个状态 s都要进行一系列复杂的计算。 首先是分支度量计算对于每个状态和每个可能的输入比特计算从当前状态转移到下一状态的分支度量。以硬判决为例通过比较接收序列中当前时刻的符号与假设分支输出的符号计算它们之间的汉明距离作为分支度量值。接着进行加 - 比较 - 选择ACS操作将所有进入该状态的路径的度量值即前一状态的路径度量值加上当前分支度量值相加并与当前状态的幸存路径度量进行比较。选择具有最小度量值的路径作为新的幸存路径更新路径度量和路径历史。例如在某一时刻有两条路径可以到达状态 s路径 1 从状态 s1 转移过来路径 1 的前一状态 s1 的路径度量值为 5当前分支度量值为 3路径 2 从状态 s2 转移过来路径 2 的前一状态 s2 的路径度量值为 4当前分支度量值为 2。通过计算路径 1 到达状态 s 的路径度量值为 5 3 8路径 2 到达状态 s 的路径度量值为 4 2 6比较后发现路径 2 的度量值更小所以选择路径 2 作为到达状态 s 的幸存路径更新状态 s 的路径度量为 6并记录路径 2 的前一状态为 s2。在这个过程中需要不断地存储和更新每个状态和时刻的幸存路径历史信息以便后续回溯使用。 终止阶段发生在达到接收序列的末尾时此时需要选择具有最小路径度量的状态作为最终状态。这个最终状态代表了整个解码过程中最有可能的结束状态从这个状态开始回溯就能够得到最有可能的原始信息序列。 回溯阶段从最终状态开始沿着之前记录的幸存路径历史信息回溯到初始状态。在回溯过程中根据每个状态记录的前一状态信息逐步确定最优路径上每个状态的输入比特从而得到最有可能的原始信息序列。例如最终状态的前一状态是 s3s3 的前一状态是 s5以此类推直到回溯到初始状态。在回溯过程中根据状态转移的对应关系确定每个状态转移时的输入比特将这些输入比特依次排列就得到了原始信息序列。下图展示了 Viterbi 解码算法的流程从图中可以清晰看到各个步骤之间的关系和执行顺序。 图Viterbi 解码算法流程 2.1.5 译码算法举例与复杂度分析 为了更直观地理解 Viterbi 译码算法的工作过程以一个简单的 (2, 1, 3) 卷积码为例进行说明。假设发送端发送的信息序列为 1011经过卷积码编码器编码后通过噪声信道传输到接收端接收端接收到的序列为 11010100这里只是示例简单理解原理即可不用纠结细节。 首先构建 (2, 1, 3) 卷积码的网格图确定初始状态的路径度量为 0其他状态路径度量为无穷大。在 t 1 时刻从初始状态 00 出发若输入比特为 0转移到状态 00输出码字为 00与接收序列的第一个符号 11 的汉明距离为 2若输入比特为 1转移到状态 10输出码字为 11与接收序列的第一个符号 11 的汉明距离为 0。此时选择汉明距离为 0 的路径即输入比特为 1转移到状态 10 的路径作为幸存路径更新状态 10 的路径度量为 0。 在 t 2 时刻从状态 10 出发若输入比特为 0转移到状态 01输出码字为 01与接收序列的第二个符号 01 的汉明距离为 0若输入比特为 1转移到状态 11输出码字为 11与接收序列的第二个符号 01 的汉明距离为 2。比较两条路径的度量值选择汉明距离为 0 的路径即输入比特为 0转移到状态 01 的路径作为幸存路径更新状态 01 的路径度量为 00 0 0。 在 t 3 时刻从状态 01 出发若输入比特为 0转移到状态 10输出码字为 10与接收序列的第三个符号 10 的汉明距离为 0若输入比特为 1转移到状态 11输出码字为 00与接收序列的第三个符号 10 的汉明距离为 2。比较两条路径的度量值选择汉明距离为 0 的路径即输入比特为 0转移到状态 10 的路径作为幸存路径更新状态 10 的路径度量为 00 0 0。 在 t 4 时刻从状态 10 出发若输入比特为 0转移到状态 01输出码字为 01与接收序列的第四个符号 00 的汉明距离为 1若输入比特为 1转移到状态 11输出码字为 11与接收序列的第四个符号 00 的汉明距离为 2。比较两条路径的度量值选择汉明距离为 1 的路径即输入比特为 0转移到状态 01 的路径作为幸存路径更新状态 01 的路径度量为 10 1 1。 经过这四个时刻的计算完成了对接收序列的 Viterbi 译码。在整个过程中通过不断比较不同路径的汉明距离选择最优的幸存路径从而确定最有可能的发送信息序列。 最终根据各个时刻的幸存路径回溯得到译码后的信息序列。回溯过程如下从最后时刻的状态 01 开始因为在 t 4 时刻是从状态 10 输入 0 转移到状态 01 的所以得到最后一个译码比特为 0在 t 3 时刻是从状态 01 输入 0 转移到状态 10 的得到倒数第二个译码比特为 0在 t 2 时刻是从状态 10 输入 0 转移到状态 01 的得到倒数第三个译码比特为 0在 t 1 时刻是从状态 00 输入 1 转移到状态 10 的得到第一个译码比特为 1。所以回溯得到的译码信息序列为 1000与原始发送的信息序列 1011 存在一定差异这是由于噪声信道对传输信号造成了干扰使得接收序列发生了误码。但 Viterbi 译码算法在一定程度上能够纠正部分错误提高通信的可靠性。 #mermaid-svg-9xEE5EymE7eKZd9s {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .error-icon{fill:#552222;}#mermaid-svg-9xEE5EymE7eKZd9s .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-9xEE5EymE7eKZd9s .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-9xEE5EymE7eKZd9s .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-9xEE5EymE7eKZd9s .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-9xEE5EymE7eKZd9s .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-9xEE5EymE7eKZd9s .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-9xEE5EymE7eKZd9s .marker{fill:#333333;stroke:#333333;}#mermaid-svg-9xEE5EymE7eKZd9s .marker.cross{stroke:#333333;}#mermaid-svg-9xEE5EymE7eKZd9s svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-9xEE5EymE7eKZd9s .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .cluster-label text{fill:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .cluster-label span{color:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .label text,#mermaid-svg-9xEE5EymE7eKZd9s span{fill:#333;color:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .node rect,#mermaid-svg-9xEE5EymE7eKZd9s .node circle,#mermaid-svg-9xEE5EymE7eKZd9s .node ellipse,#mermaid-svg-9xEE5EymE7eKZd9s .node polygon,#mermaid-svg-9xEE5EymE7eKZd9s .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-9xEE5EymE7eKZd9s .node .label{text-align:center;}#mermaid-svg-9xEE5EymE7eKZd9s .node.clickable{cursor:pointer;}#mermaid-svg-9xEE5EymE7eKZd9s .arrowheadPath{fill:#333333;}#mermaid-svg-9xEE5EymE7eKZd9s .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-9xEE5EymE7eKZd9s .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-9xEE5EymE7eKZd9s .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-9xEE5EymE7eKZd9s .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-9xEE5EymE7eKZd9s .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-9xEE5EymE7eKZd9s .cluster text{fill:#333;}#mermaid-svg-9xEE5EymE7eKZd9s .cluster span{color:#333;}#mermaid-svg-9xEE5EymE7eKZd9s div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-9xEE5EymE7eKZd9s :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;}#mermaid-svg-9xEE5EymE7eKZd9s .survivor*{fill:#ffd700!important;stroke:#c00!important;}#mermaid-svg-9xEE5EymE7eKZd9s .survivor span{fill:#ffd700!important;stroke:#c00!important;} ¹⁄₁₁ (0) 0/00 (2) 0/01 (0) ¹⁄₁₁ (2) 0/10 (0) ¹⁄₀₀ (2) 0/01 (1) ¹⁄₁₁ (2) t0: 00 (0) t1: 10 (0) t1: 00 (2) t2: 01 (0) t2: 11 (2) t3: 10 (0) t3: 11 (2) t4: 01 (1) t4: 11 (2) 然而Viterbi 译码算法的复杂度随约束长度的增加而指数增长。对于 (n, k, L) 卷积码其中 L 为约束长度在每个时刻每个状态都有 2k 条可能的路径需要计算和比较。随着时间的推进路径数量会迅速增加。例如当约束长度 L 3 时在每个时刻每个状态需要比较 21 * 23-1 8 条路径当约束长度 L 5 时每个状态需要比较 21 * 25-1 32 条路径。这种指数增长的复杂度使得在实际应用中当约束长度较大时Viterbi 译码算法的计算量和存储需求会变得非常庞大对硬件资源和计算能力提出了很高的要求。为了降低复杂度在实际应用中常采用一些优化技术如量化技术减少计算精度要求剪枝技术去除一些不太可能的路径等以提高算法的可行性和效率。 对于(n, k, L)卷积码的维特比译码算法其复杂度主要体现在路径度量计算和幸存路径存储两方面 计算复杂度在每个时刻每个状态有 2 k 2^k 2k条可能路径需要计算和比较。由于存在 2 L − 1 2^{L - 1} 2L−1个状态所以每个时刻的计算量为 2 k × 2 L − 1 2 k L − 1 2^k\times2^{L - 1}2^{k L - 1} 2k×2L−12kL−1。假设译码长度为 N N N则总的计算复杂度为 O ( N × 2 k L − 1 ) O(N\times2^{k L - 1}) O(N×2kL−1)随着约束长度 L L L增加计算量呈指数增长。存储复杂度需存储每个状态的幸存路径和路径度量值。每个状态有 2 L − 1 2^{L - 1} 2L−1个每个幸存路径长度最大为 N N N所以存储路径的空间复杂度为 O ( N × 2 L − 1 ) O(N\times2^{L - 1}) O(N×2L−1) 存储路径度量值的空间复杂度为 O ( 2 L − 1 ) O(2^{L-1}) O(2L−1)。总的存储复杂度也是随着约束长度 L L L的增加呈指数增长。 维特比译码算法的复杂度较高尤其在约束长度较大时对计算资源和存储资源要求苛刻这也是实际应用中需要优化技术来降低复杂度的原因。如果你还想了解这些优化技术的具体实现细节欢迎随时提问。 2.1.6 算法代码示例 #include iostream #include vector #include climits #include algorithm// 计算汉明距离 int hammingDistance(int a, int b) {int xorResult a ^ b;int distance 0;while (xorResult) {distance xorResult 1;xorResult 1;}return distance; }// (2, 1, 3) 卷积码编码器函数 std::vectorint convolutionalEncoder(const std::vectorint input) {std::vectorint output;int state 0;for (int bit : input) {int bit1 (bit ((state 1) 1) (state 1)) % 2;int bit2 (bit ((state 2) 1) (state 1)) % 2;output.push_back(bit1);output.push_back(bit2);state ((state 1) | bit) 7;}return output; }// Viterbi 译码函数 std::vectorint viterbiDecoder(const std::vectorint received) {int numStates 8; // (2, 1, 3) 卷积码有 2^3 8 个状态int numSteps received.size() / 2;std::vectorstd::vectorint pathMetrics(numSteps 1, std::vectorint(numStates, INT_MAX));std::vectorstd::vectorint survivorPaths(numSteps 1, std::vectorint(numStates, -1));// 初始化pathMetrics[0][0] 0;for (int t 1; t numSteps; t) {for (int state 0; state numStates; state) {int prevState1 (state 1) 7;int prevState2 ((state 1) | 1) 7;int inputBit1 0;int output1 ((inputBit1 ((prevState1 1) 1) (prevState1 1)) % 2) * 2 ((inputBit1 ((prevState1 2) 1) (prevState1 1)) % 2);int receivedSymbol received[2 * (t - 1)] * 2 received[2 * (t - 1) 1];int metric1 pathMetrics[t - 1][prevState1] hammingDistance(output1, receivedSymbol);int inputBit2 1;int output2 ((inputBit2 ((prevState2 1) 1) (prevState2 1)) % 2) * 2 ((inputBit2 ((prevState2 2) 1) (prevState2 1)) % 2);int metric2 pathMetrics[t - 1][prevState2] hammingDistance(output2, receivedSymbol);if (metric1 metric2) {pathMetrics[t][state] metric1;survivorPaths[t][state] prevState1;} else {pathMetrics[t][state] metric2;survivorPaths[t][state] prevState2;}}}// 回溯std::vectorint decoded(numSteps);int finalState std::min_element(pathMetrics[numSteps].begin(), pathMetrics[numSteps].end()) - pathMetrics[numSteps].begin();for (int t numSteps; t 0; –t) {int prevState survivorPaths[t][finalState];decodedt - 1 1;finalState prevState;}return decoded; }int main() {std::vectorint received {1, 1, 0, 1, 0, 1, 0, 0};std::vectorint decoded viterbiDecoder(received);std::cout 译码后的信息序列: ;for (int bit : decoded) {std::cout bit;}std::cout std::endl;return 0; }