Pless, Vera. Introduction to the theory of error-correcting codes. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons. 1982. ISBN 0-471-08684-3.
J.H. van Lint. Introduction to Coding Theory. GTM86 2nd. Springer-Verlag. 1992. ISBN 3-540-54894-7.
参考文献
^Feldman, Jon; Wainwright, Martin J.; Karger, David R. Using Linear Programming to Decode Binary Linear Codes 51 (3). March 2005: 954–972. doi:10.1109/TIT.2004.842696.|journal=被忽略 (帮助)
^Aji, Srinivas M.; McEliece, Robert J. The Generalized Distributive Law. IEEE Transactions on Information Theory. March 2000, 46 (2): 325–343. doi:10.1109/18.825794.
行進 24, 2023
译码方法, 在编码理论中, 译码, 英語, decoding, 是将接收到的消息译成给定码元的码字, 英语, codewords, 的过程, 有许多常用的将消息映射到码字的方法, 这些方法通常用于在有噪信道, 如二元对称信道, 英语, binary, symmetric, channel, 传输后恢复消息, 目录, 记号, 理想观察者译码, 译码约定, 最大似然译码, 最小距离译码, 校正子译码, 部分响应最大似然法, 维特比译码器, 参见, 来源, 参考文献记号, 编辑c, displaystyle, subse. 在编码理论中 译码 英語 decoding 是将接收到的消息译成给定码元的码字 英语 codewords 的过程 有许多常用的将消息映射到码字的方法 这些方法通常用于在有噪信道 如二元对称信道 英语 binary symmetric channel 传输后恢复消息 目录 1 记号 2 理想观察者译码 2 1 译码约定 3 最大似然译码 4 最小距离译码 5 校正子译码 6 部分响应最大似然法 7 维特比译码器 8 参见 9 来源 10 参考文献记号 编辑C F 2 n displaystyle C subset mathbb F 2 n 是指长度为 n displaystyle n 的二元码 英语 binary code x y displaystyle x y 为 F 2 n displaystyle mathbb F 2 n 的元素 而 d x y displaystyle d x y 为它们之间的距离 理想观察者译码 编辑给定信号 x F 2 n displaystyle x in mathbb F 2 n 则理想观察者译码会生成码字 y C displaystyle y in C 该过程得到这个解 P displaystyle mathbb P y 发送 x 接收 例如 在传输后可以选择最接近消息 x displaystyle x 的码字 y displaystyle y 译码约定 编辑 所有码字都不满足期望概率 可能会有多于一个码字其转变为接收到的消息的似然性相等 在此情况下 发送方和接收方必须提前对译码约定达成一致 广泛使用的约定有 请求重发码字 自动重传请求 从最接近码字的集合中随机选取码字最大似然译码 编辑更多信息 最大似然估计 给定一个接收到的码字 x F 2 n displaystyle x in mathbb F 2 n 最大似然译码选取可以最大化 P displaystyle mathbb P x 接收 y 发送 的码字 y C displaystyle y in C 即会最大化发送 y displaystyle y 条件下 接收到 x displaystyle x 的概率 如果所有码字的发送概率都相等的话 则此方法与理想观察者译码等价 事实上 根据贝叶斯定理 P x received y sent P x received y sent P y sent P y sent x received P x received P y sent displaystyle begin aligned mathbb P x mbox received mid y mbox sent amp frac mathbb P x mbox received y mbox sent mathbb P y mbox sent amp mathbb P y mbox sent mid x mbox received cdot frac mathbb P x mbox received mathbb P y mbox sent end aligned 在固定 P x received displaystyle mathbb P x mbox received 下 可以重建 x displaystyle x 而由于所有符号等可能地发送 P y sent displaystyle mathbb P y mbox sent 为常数 于是 y displaystyle y 的函数 P x received y sent displaystyle mathbb P x mbox received mid y mbox sent 在最大化的同时 P y sent x received displaystyle mathbb P y mbox sent mid x mbox received 也会最大化 因而遵循该断言 与理想观察者译码一样 对于非唯一译码 也需要事先达成译码约定 最大似然译码问题可以建模为整数规划问题 1 最大似然译码问题是 乘积函数边缘化 问题 已通过运用广义分配律 英语 generalized distributive law 解决 的一个实例 2 最小距离译码 编辑给定一个接收到的码字 x F 2 n displaystyle x in mathbb F 2 n 最小距离译码会选出使汉明距离最小化的码字 y C displaystyle y in C d x y i x i y i displaystyle d x y i x i not y i 即选取尽可能接近 x displaystyle x 的码字 y displaystyle y 注意到如果一个离散无记忆信道 英语 discrete memoryless channel 误差概率 p displaystyle p 小于二分之一 则最小距离译码等价于最大似然译码 因为若 d x y d displaystyle d x y d 则 P y received x sent 1 p n d p d 1 p n p 1 p d displaystyle begin aligned mathbb P y mbox received mid x mbox sent amp 1 p n d cdot p d amp 1 p n cdot left frac p 1 p right d end aligned 该式 由于 p 小于二分之一 是通过最小化 d 来最大化的 最小距离译码也叫最近邻居译码 可以用标准阵列 英语 standard array 来辅助或自动译码 在满足下列条件的情况下 最小距离译码是一种合理的译码方法 出现差错的概率 p displaystyle p 与符号的位置无关 差错是独立事件 消息中某一位置出现差错不会影响其他位置这些假设对于在二元对称信道 英语 binary symmetric channel 中传输时合理的 对于其他介质可能不适用 比如在DVD中 光盘上的一个划痕就可以引起很多相邻的符号或码字产生错误 与其他译码方法一样 对于非唯一译码 需要事先达成译码约定 校正子译码 编辑伴随式译码 英語 syndrome decoding 是在有噪信道 即会有产生差错的信道 译码线性码 英语 linear code 的一种高效的方法 本质上 伴随式译码是最小距离译码使用一个简化的查找表 线性码允许这种译码 假设 C F 2 n displaystyle C subset mathbb F 2 n 是奇偶檢驗矩陣为 H displaystyle H 的 长为 n displaystyle n 最小距离为 d displaystyle d 的线性码 则显然 C displaystyle C 有纠正信道产生的 t d 1 2 displaystyle t left lfloor frac d 1 2 right rfloor 个错的能力 因为如果产生了不到 t displaystyle t 个差错 则最小距离译码仍可以正确译出传输错误的码字 现在假设码字 x F 2 n displaystyle x in mathbb F 2 n 在该信道中发送 发生错误图样 e F 2 n displaystyle e in mathbb F 2 n 则收到 z x e displaystyle z x e 普通的最小距离译码会在大小为 C displaystyle C 的表中找向量 z displaystyle z 最接近的匹配 即对于所有 y C displaystyle y in C 元素 不一定唯一 c C displaystyle c in C 都满足 d c z d y z displaystyle d c z leq d y z 伴随式译码利用了奇偶校验矩阵的性质 对于所有 x C displaystyle x in C H x 0 displaystyle Hx 0 接收到的 z x e displaystyle z x e 的伴随式定义为 H z H x e H x H e 0 H e H e displaystyle Hz H x e Hx He 0 He He 在二元对称信道 英语 Binary symmetric channel 中进行最大似然译码 要从大小为 2 n k displaystyle 2 n k 的预计算表格中查询 将 H e displaystyle He 映射到 e displaystyle e 注意到这比起标准阵列译码 英语 standard array 的复杂度已经明显减小了 不过 在假设传输中不会超过 t displaystyle t 个差错的前提下 接收方仅仅需要在更小的表格 对于二元码来说 中查找 H e displaystyle He 这个值 i 0 t n i lt C displaystyle begin matrix sum i 0 t binom n i lt C end matrix 该表是针对所有可能的错误图样 e F 2 n displaystyle e in mathbb F 2 n 下 H e displaystyle He 的预计算值的 已知 e displaystyle e 译码 x displaystyle x 就不是难事了 x z e displaystyle x z e 部分响应最大似然法 编辑部分响应最大似然法 PRML 是一种将弱模拟信号从磁盘或磁带驱动器的的磁头转换成数字信号的方法 维特比译码器 编辑维特比译码器使用维特比算法译码已经用基于卷积码的前向錯誤更正编码的比特流 汉明距离用来作为硬判决维特比译码器的度量 欧氏距离的平方用作软判决译码器的度量 参见 编辑差错检测与校正来源 编辑Hill Raymond A first course in coding theory Oxford Applied Mathematics and Computing Science Series Oxford University Press 1986 ISBN 0 19 853803 0 Pless Vera Introduction to the theory of error correcting codes Wiley Interscience Series in Discrete Mathematics John Wiley amp Sons 1982 ISBN 0 471 08684 3 J H van Lint Introduction to Coding Theory GTM 86 2nd Springer Verlag 1992 ISBN 3 540 54894 7 参考文献 编辑 Feldman Jon Wainwright Martin J Karger David R Using Linear Programming to Decode Binary Linear Codes 51 3 March 2005 954 972 doi 10 1109 TIT 2004 842696 journal 被忽略 帮助 Aji Srinivas M McEliece Robert J The Generalized Distributive Law IEEE Transactions on Information Theory March 2000 46 2 325 343 doi 10 1109 18 825794 取自 https zh wikipedia org w index php title 译码方法 amp oldid 64183931, 维基百科,wiki,书籍,书籍,图书馆,