错误检测与纠正
在计算机科学和通信的信息论和编码理论应用中，错误检测和纠正（）或错误控制（error control）是在不可靠的通信信道上可靠地传送数字数据的技术。许多通信信道会经受信道噪声，因此可能在源至接收器的传输期间引入错误。错误检测技术能够检测这样的错误，而错误纠正能在不少情况下重建原始数据。 定义 该术语的一般定义如下： 错误检测是检测发射机到接收机的传输期间由噪声或其他原因所致的错误。 错误纠正是检测错误并重建无错误的原样数据。 历史 错…
标签：#错误检测与校正
共 27 篇文章
散列函數
散列函数（）又称-{zh-cn:散列算法、哈希函数; zh-tw:雜湊演算法}-，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据计算成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（又叫哈希值）（，，，或）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。如果在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更…
BCH码
BCH码（BCH codes、Bose–Chaudhuri–Hocquenghem codes）為取自Bose、Ray-Chaudhuri与Hocquenghem的缩写，是编码理论尤其是纠错码中研究得比较多的一种编码方法。用术语来说，BCH码是用于校正多个随机错误模式的多级、循环、错误校正、变长数字编码。BCH码也可以用于质数级或者质数的幂级的多级相移键控。11级的BCH码已经用于表示10进制数外加一个符号位。 构建 BCH 码使用有限…
汉明码
在電信領域中，漢明碼（），也称为海明码，是推广得到的一種线性纠错码，由理查德·衛斯里·漢明于1950年發明。相比而言，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。汉明码是，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。 用數學术语来说，漢明碼是一種二元線性碼。對於所有整數 ，存在一个分组长度 、 编码。因此汉明码的码率为 ，对于最小距离为3、分组长度为 的码来说是最高的。漢明碼的奇偶檢驗矩陣的是通過列出所…
编码理论
是一种广泛使用数据压缩以补偿阅读速度缓慢的编码。]] 编码理论（）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、，最近也用于网络编码中。不同学科（如信息论、電機工程學、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。 编码共分四类： 数据压缩（或信源编码） 前向錯誤更正（或信道编码） 加密编码 线路码 数据压缩和前向錯誤更正可以。…
涡轮码
涡轮码（）是信息论中一种前向纠错的编码技术，发明于1990至1991年间，并于1993年首次发表。涡轮码是首个得以接近香农极限的现实可行的编码，在低信噪比条件下有着优越的性能，广泛运用于3G/4G移动通信（如UMTS与LTE）、深空卫星通信等领域。 涡轮码的解码过程通过一个反馈环路迭代进行，因类似于内燃机中涡轮增压器的工作过程而得名。 以人工智能的角度而言，涡轮码的解码可看作是贝叶斯网络上的循环置信度传播（loopy belief pr…
帧校验序列
的FCS]] 帧校验序列（，FCS）是在网络传输协议中添加到帧中的错误检测代码。 帧的功能是将负载数据从源发送到目的地。 目的 所有帧以及其中包含的字元、字节和字段都非常容易产生错误。FCS字段包含一个由源节点根据帧中的数据计算出来的数字。这个数字被添加到帧的末尾，在目的节点接收到该帧后，将根据接收到的帧数据重新计算FCS，并与帧中原本包含的FCS进行比较。如果计算产生的FCS和收到的FCS不一致，就可以断定该帧存在错误。 FCS只能做…
機員資源管理
機員資源管理（Crew Resource Management）或駕駛艙資源管理（Cockpit Resource Management (CRM)）為一套程序及訓練系統，為減少人為錯誤而產生嚴重後果。此系統主要為改進航空飛行時的安全，CRM集中於機組人員之間，人與人的溝通、領導力、及決定能力。此訓練最初源於美國太空總署因很多航空的意外均為人為錯誤，而進行的一項關於飛機人員行為科學的研究，目的是為了減少因機員失誤而造成的空難。從此廣泛應…
確認訊息
確認訊息也稱為ACK訊息，是在電腦網路、电信或总线中通訊協定的一部份，是設備或是行程發出的訊息，表示接收端之前已收到資料。否定应答也稱為NAK訊息或是NACK訊息則是接收端發出，拒絕之前收到資料，或是表示之前收到資料有誤的訊息。確認訊息和NAK訊息可以讓發送端知道接收端的情形，以便發送端對應調整狀態。 許多通訊協定中會有檢查碼來驗證负载以及信头的完整性。檢查碼可以用來檢查資料是否受損。若接收到的訊息，其檢查碼是無效的（依照規則算出的檢查…
卢恩算法
卢恩算法（），也称为“模10”（Mod 10）算法，是一种简单的校验和算法，一般用于验证身份识别码，例如发卡行识别码、国际移动设备识别码，美国号码，或是。该算法由IBM科学家创造，专利于1954年1月6日申请，1960年8月23日颁证，美国专利号2950048。 该算法现已属于公有领域并得到了广泛的应用，例如ISO/IEC 7812-1。它不是一种安全的加密哈希函数，设计它的目的只是防止意外出错而不是恶意攻击。 描述 卢恩算法会通过校验…
维特比算法
维特比算法（）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。 维特比算法由安德鲁·维特比于1967年提出，用于在数字通信链路中解卷积以消除噪音。此算法被…
伯利坎普-梅西算法
伯利坎普－梅西算法（，简称B-M算法）用来构造一个尽可能短的线性反馈移位寄存器（，LFSR）来产生一个有限二元序列s^N，同时，该算法也给出了s^N的线性复杂度。该算法是一个多项式时间的迭代算法，以N长二元序列a_0,a_1,...,a_{N-1}为输入，输出产生给序列式的最短LFSR的特征多项式f_N(x)及该LFSR的线性复杂度L(s^N)。 這一算法由埃爾溫·伯利坎普與詹姆斯·梅西發明。
伯利坎普-韦尔奇算法
伯利坎普－韦尔奇算法（）是一種用於高效地解碼BCH碼與里德-所羅門碼的演算法，其名取自埃尔温·伯利坎普與勞埃德·韋爾奇。伯利坎普－韦尔奇算法的優點在於這一演算法僅需利用矩陣運算。這一演算法的時間複雜度為O(N^3)。 演算法 伯利坎普－韦尔奇算法通常被用於解碼里德-所羅門碼。假使在有限體GF(q)上有n個數字m_1, \dots , m_n，利用RS碼編為n-1次多項式P(i)=m_i。如果已知傳輸信道會錯誤傳輸k個值，那麼RS碼可以傳…
校验码
校验码（）通常是一组数字的最后一位，由前面的数字通过某种运算得出，用以检验该组数字的正确性。常见的校验码有身份证號的最后一位，ISBN号码的最后一位等。 各地身份证算法 不同的校验码的算法常常不同，下面以身份证的校验码为例 中国大陆 按照中华人民共和国国家标准GB11643-1999规定中华人民共和国公民身份号码校验码的计算方法即为ISO 7064:1983.MOD 11-2校验码计算法。 假设某一17位数字是 #计算17位数字各位数字…
拉丁方陣
拉丁方陣（）是一種 n × n 的方陣，在這種 n × n 的方陣裡，恰有 n 種不同的元素，每一種不同的元素在同一行或同一列裡只出現一次。以下是兩個拉丁方陣舉例： \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d…
前向錯誤更正
前向錯誤更正（，缩写FEC）或信道编码（）是一種在單向通信系統中控制传输錯誤的技術，通過連同數據發送額外的資訊進行錯誤恢復，以降低比特误码率。FEC又分为带内FEC和带外FEC。FEC的處理往往發生在第一次收到數字信號的早期階段。也就是說，糾錯電路往往是不可分割的一部分，模擬到數字的轉換過程中，還涉及數字调制解調，或線路編碼和解碼。 FEC采用预先确定的算法，以添加冗余的方式进行传输。通常每一种FEC方法都直接以该编码命名，这类编码被称…
奇偶校验位
奇偶校验位（）或校验比特（）是一个表示给定位数的二进制数中1的个数是奇数还是偶数的二进制数。奇偶校验位是最简单的错误检测码。 类型 奇偶校验位有两种类型：偶校验位与奇校验位。 以偶校验位來說，如果一组给定数据位中1的个数是奇数，補一個bit(0或1)在最右方，使得总的1的个数是偶数。例：0000001, 補一個bit为1, 00000011。 以奇校验位來說，如果给定一组数据位中1的个数是奇数，補一個bit(0或1)在最右方，使得总的1…
里德-所罗门码
里德-所罗门码（，簡稱里所码或 ）是一种前向錯誤更正的信道编码，对由校正过采样数据所产生的有效多项式。编码过程首先在多个点上对这些多项式求冗余，然后将其传输或者存储。对多项式的这种超出必要值的采样使得多项式超定（过限定）。当接收器正确地收到足够的点后，它就可以恢复原来的多项式，即使接收到的多项式上有很多点被噪声干扰失真。 里德-所罗门码被广泛地应用于各种商业用途，最显著的是在CD、DVD、蓝光光盘和QR code上的使用；在数据传输中，…
冗余校验
在通信领域中，冗余校验是消息中附加的用于错误检测与错误校正的数据。 任何一个散列函数都可以用于冗余检校验。最简单的冗余校验，叫作校验和，它包括校验位、校验碼以及纵向冗余校验（LRC，longitudinal redundancy check）。其他类型的冗余校验包括循环冗余校验（CRC，cyclic redundancy check）、水平冗余校验、竖直冗余校验以及密碼雜湊函數。 奇偶校验仅仅是一个错误检测的机制，根据所用奇校验与偶校验…
三重模塊冗餘
組成的多數表決電路]] 在计算机科学中的三重模塊冗餘（triple modular redundancy，有時也稱為triple-mode redundancy）簡稱TMR，屬於多重模塊冗餘（N-modular redundancy）的容錯形式，用三個相同的系統執行同一功能，再透過多數表決（majority-voting）系統，取多數的輸出為最後的輸出。若三個系統中只有一個損壞，另外二個正常，多數表決系統會使用二個對的輸出，成為最後的輸…