主題
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

使用 探索

參考文獻

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.

在 上引用

糾錯碼

請這樣引用

Weisstein, Eric W. "糾錯碼。" 來自 --一個 資源。 https://mathworld.tw/Error-CorrectingCode.html

主題分類