主题
Search

纠错码

纠错码是一种算法，用于表达数字序列，以便可以检测和纠正引入的任何错误（在一定限制内），基于剩余的数字。对纠错码和相关数学的研究被称为编码理论。

错误检测比错误纠正简单得多，并且一个或多个“校验”位通常嵌入在信用卡号码中，以便检测错误。早期的太空探测器如水手号使用了一种称为分组码的纠错码，而最近的太空探测器使用卷积码。纠错码也用于 CD 播放器、高速调制解调器和蜂窝电话。调制解调器在计算校验和时使用错误检测，校验和是给定传输中数字的和模某个数。ISBN（用于标识书籍）也包含一个校验位。

对 13 位数字进行有效校验包括以下步骤。将数字写成数字字符串 a_1a_2a_3...a_(13)。取 a_1+a_3+...+a_(13) 并将其加倍。现在加上奇数位置中数字的数量，这些数字 >4 大于 4，加到这个数字上。现在加上 a_2+a_4+...+a_(12)。校验数是使最后一位数字变为 0 所需的数字。此方案检测所有单个数字错误以及除 0 和 9 之外的所有相邻数字的换位。

设 A(n,d) 表示最大数量的 n (0,1) 向量，这些向量的任意两个都至少在 d 个位置上不同。相应的向量可以纠正 [(d-1)/2] 个错误。A(n,d,w) 是具有精确 A(n,d)s 和 w 个 1 的数量 (Sloane and Plouffe 1995)。由于 n 向量不可能在 d>n 个位置上不同，并且由于在所有 n 个位置上不同的 n 向量划分为两个不同的集合，

A(n,d)={1 n<d; 2 n=d.
(1)

可以通过标记 2^n 个 (0,1)-n 向量来找到 A(n,d) 的值，找到所有无序对 (a_i,a_j)，其中 n 向量彼此之间至少在 d 个位置上不同，从这些无序对形成一个图，然后找到该图的团数。遗憾的是，对于给定的图，找到团的大小是一个 NP 完全问题。

dOEISA(n,d)
1A0000792, 4, 8, 16, 32, 64, 128, ...
21, 2, 4, 8, ...
31, 1, 2, 2, ...
4A0058641, 1, 1, 2, 4, 8, 16, 20, 40, ...
51, 1, 1, 1, 2, ...
6A0058651, 1, 1, 1, 1, 2, 2, 2, 4, 6, 12, ...
71, 1, 1, 1, 1, 1, 2, ...
8A0058661, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, ...

另请参阅

校验和, 团, 团数, 编码理论, 有限域, Golay 码, Hadamard 矩阵, 半立方体图, 汉明码, ISBN, 完美码, UPC

使用 Wolfram|Alpha 探索

参考文献

Baylis, J. Error Correcting Codes: A Mathematical Introduction. Boca Raton, FL: CRC Press, 1998.Berlekamp, E. R. Algebraic Coding Theory, rev. ed. New York: McGraw-Hill, 1968.Brouwer, A. E.; Shearer, J. B.; Sloane, N. J. A.; 和 Smith, W. D. "A New Table of Constant Weight Codes." IEEE Trans. Inform. Th. 36, 1334-1380, 1990.Calderbank, A. R.; Hammons, A. R. Jr.; Kumar, P. V.; Sloane, N. J. A.; 和 Solé, P. "A Linear Construction for Certain Kerdock and Preparata Codes." Bull. Amer. Math. Soc. 29, 218-222, 1993.Conway, J. H. 和 Sloane, N. J. A. "Quaternary Constructions for the Binary Single-Error-Correcting Codes of Julin, Best and Others." Des. Codes Cryptogr. 4, 31-42, 1994.Conway, J. H. 和 Sloane, N. J. A. "Error-Correcting Codes." §3.2 in Sphere Packings, Lattices, and Groups, 2nd ed. New York: Springer-Verlag, pp. 75-88, 1993. Gachkov, I. "Error-Correcting Codes with Mathematica." http://library.wolfram.com/infocenter/MathSource/5085/.Gallian, J. "How Computers Can Read and Correct ID Numbers." Math Horizons, pp. 14-15, Winter 1993.Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 119-121, 1994.MacWilliams, F. J. 和 Sloane, N. J. A. The Theory of Error-Correcting Codes. Amsterdam, Netherlands: North-Holland, 1977.Sloane, N. J. A. Sequences A000079/M1129, A005864/M1111, A005865/M0240, and A005866/M0226 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. 和 Plouffe, S. Figure M0240 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

在 Wolfram|Alpha 上引用

纠错码

请这样引用

Weisstein, Eric W. "纠错码。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/Error-CorrectingCode.html

主题分类