#187 · Error-Correcting Codes

A faint whisper of data, sent across billions of kilometres from the edge of our solar system, reaches Earth with every bit intact. Or the familiar whir of a compact disc, playing perfectly despite visible scratches. Both rely on an unseen layer of meticulous redundancy.

This quiet miracle, the detection and correction of errors in transmitted or stored information, underpins much of our digital world. It is a field born of frustration and mathematical insight, rooted in the understanding that noise and imperfection are inherent in every communication channel. Instead of merely flagging errors and demanding re-transmission – an impossible feat for deep-space probes or a trivial inconvenience for everyday media – error-correcting codes build resilience directly into the message itself.

The fundamental concept is simple: add carefully structured extra information to the original data. This redundancy allows a receiver not only to pinpoint where corruption has occurred but often to reconstruct the original, unblemished data without needing to ask for a resend. The cost is bandwidth, a greater volume of bits sent than strictly necessary for the original message, but the payoff is reliability, even in the most hostile environments.

Hamming's Insight and the Birth of Parity The story of modern error correction begins in the late 1940s, in the hallowed halls of [[Bell Labs]]. [[Richard Hamming]], a mathematician working with early computing machines, grew increasingly annoyed by the frequent crashes caused by single-bit errors in punch card readers. These machines would halt, dump their memory, and force him to restart his computations, often over the weekend. His colleagues' solution was to add a single [[parity bit]] to each block of data – an extra bit that simply indicated whether the number of '1's in the block was even or odd. This allowed for error detection, but not correction. If an error was found, the machine simply stopped.

Hamming realised that if one could determine *which* bit was in error, rather than just *that* an error existed, then correction became possible. In 1950, he published his seminal work introducing Hamming codes, the first family of error-correcting codes capable of identifying and fixing single-bit errors. His breakthrough was to encode information such that the position of any single error could be uniquely determined from a set of calculated parity checks. It was a foundational step, moving beyond simple error detection to proactive error repair.

The Workhorse: Reed-Solomon Codes While Hamming codes proved invaluable for certain applications, the real world often throws more than just single-bit errors. Burst errors – where several consecutive bits are corrupted – are common in physical media like scratched CDs or noisy radio channels. For these scenarios, more robust codes were needed. Enter [[Reed-Solomon code]]s, first conceived in 1960 by Irving Reed and Gustave Solomon. These block codes operate on symbols (groups of bits) rather than individual bits, making them exceptionally good at handling burst errors.

Reed-Solomon codes achieve this by treating data as polynomials over finite fields. The encoder evaluates this polynomial at several points, and these evaluated points, along with the original data, are transmitted. The receiver can then reconstruct the original polynomial even if some points are lost or corrupted, much like determining a curve from a few known points. This mathematical elegance made them ubiquitous. They are the backbone of digital audio (CDs), video (DVDs, Blu-ray), QR codes, and are critical for deep-space communications, where signals are faint and interference is constant.

Reaching for the Shannon Limit The theoretical limit of reliable communication over a noisy channel was established by [[Claude Shannon]] in 1948 with his noisy-channel coding theorem. Shannon's work revealed that there's a maximum rate at which information can be transmitted with arbitrarily small error probability, even in the presence of noise. For decades, engineers and mathematicians toiled to develop codes that could approach this theoretical [[Shannon limit]].

Modern error-correcting codes, such as Turbo Codes (introduced in the early 1990s) and LDPC codes (initially proposed by Robert Gallager in 1960 but largely overlooked until the late 1990s due to computational complexity), have made remarkable progress. These codes employ iterative decoding algorithms that exchange information between multiple simpler decoders, gradually improving the probability of correct decoding. LDPC codes, in particular, are now central to high-speed communication standards like DVB-S2 (digital television), WiMAX, and 10GBase-T Ethernet, pushing the boundaries of what's possible in noisy environments.

What we still don't know

While codes can approach the Shannon limit for specific channel models, real-world channels are rarely perfectly understood or static. Adapting error correction dynamically to changing noise conditions remains a complex challenge.

The computational overhead for decoding these advanced codes, though significantly reduced, is still substantial. Finding ways to achieve near-optimal performance with less computational power is an ongoing area of research, particularly for resource-constrained devices or ultra-high-speed communication.

Furthermore, most error-correcting codes are designed to handle 'bit flips' – where a 0 becomes a 1 or vice-versa. Errors involving insertions or deletions of bits, common in asynchronous data streams, are far more challenging to correct efficiently, often requiring different coding schemes or additional synchronisation mechanisms.

A scratch on a disc or a cosmic ray impact on a distant signal are no longer fatal flaws. Instead, they are momentary blips smoothed over by an elegant mathematical shield, silently ensuring the integrity of our digital universe.

从太阳系边缘穿越数十亿公里传来的微弱数据低语，到达地球时每个比特都完好无损。或者是一张光盘，尽管表面有明显划痕，依然能完美播放。这两者都依赖于一层无形的精密冗余。

这个安静的奇迹——检测并纠正传输或存储信息中的错误——支撑着我们的数字世界。这一领域诞生于挫败感和数学洞察力，其根基在于理解噪音和不完美是每个通信渠道的固有属性。与其仅仅标记错误并要求重新传输——对于深空探测器来说这是不可能完成的任务，对于日常媒体而言也是一件微不足道的麻烦事——纠错码直接在信息本身中构建了弹性。

基本概念很简单：在原始数据中加入精心设计的额外信息。这种冗余不仅使接收方能够准确地指出错误发生的位置，而且通常可以在不需要请求重新发送的情况下重建原始无损数据。代价是带宽，即发送的比特数比严格意义上的原始信息所需更多，但回报是可靠性，即使在最恶劣的环境中也是如此。

汉明的洞察与奇偶校验的诞生现代纠错的故事始于20世纪40年代末，在[[Bell Labs]]的庄严大厅中。[[Richard Hamming]]，一位与早期计算机打交道的数学家，因穿孔卡片阅读器中频繁发生的单比特错误而愈发恼火。这些机器会停止运行，清空内存，迫使他重新开始计算，常常要持续到周末。他的同事的解决方案是在每块数据中添加一个单独的[[parity bit]]——一个额外的比特，仅表示该块中“1”的数量是偶数还是奇数。这允许检测错误，但无法纠正错误。如果发现错误，机器就会停止。

汉明意识到，如果能够确定*哪个*比特出错，而不仅仅是*存在*错误，那么纠正就成为可能。1950年，他发表了开创性著作，介绍了汉明码，这是第一个能够识别并修复单比特错误的纠错码家族。他的突破在于将信息编码，使得任何单个错误的位置都可以通过一组计算出的奇偶校验来唯一确定。这是迈向基础性进展的一步，超越了简单的错误检测，实现了主动的错误修复。

工作马匹：里德-所罗门码尽管汉明码在某些应用中证明非常有价值，但现实世界往往不仅出现单比特错误。突发错误——即连续多个比特被破坏——在物理介质（如划伤的CD）或嘈杂的无线电通道中很常见。对于这些情况，需要更强大的码。于是出现了[[Reed-Solomon code]]码，最初由Irving Reed和Gustave Solomon于1960年提出。这些块码操作的是符号（比特组），而不是单个比特，因此在处理突发错误方面表现得尤为出色。

里德-所罗门码通过将数据视为有限域上的多项式来实现这一点。编码器在多个点上评估这个多项式，并将这些评估点与原始数据一起传输。接收方即使某些点丢失或损坏，也可以重建原始多项式，就像从几个已知点确定一条曲线一样。这种数学上的优雅使它们无处不在。它们是数字音频（CD）、视频（DVD、蓝光）、二维码的核心，并且对于深空通信至关重要，在信号微弱且干扰持续不断的环境中发挥着关键作用。

接近香农极限 1948年，[[Claude Shannon]]通过他的噪声信道编码定理确立了在噪声信道上可靠通信的理论极限。香农的工作揭示了即使在存在噪声的情况下，信息也可以以最大速率传输，且错误概率可以任意小。几十年来，工程师和数学家们努力开发能够接近这一理论[[Shannon limit]]的码。

现代纠错码，如Turbo码（20世纪90年代初引入）和LDPC code码（最初由Robert Gallager于1960年提出，但由于计算复杂性在20世纪90年代末才被广泛忽视），取得了显著进展。这些码使用迭代解码算法，在多个较简单的解码器之间交换信息，逐渐提高正确解码的概率。特别是LDPC码，现在已成为高速通信标准（如DVB-S2（数字电视）、WiMAX和10GBase-T以太网）的核心，推动了在嘈杂环境中实现的可能性的边界。

我们仍然不知道的

虽然码可以在特定信道模型中接近香农极限，但现实世界的信道很少被完全理解和静态。动态适应不断变化的噪声条件仍然是一个复杂的挑战。

尽管这些先进码的解码计算开销已经大大减少，但仍然是相当大的。找到以更少的计算能力实现接近最优性能的方法，仍然是一个持续的研究领域，尤其是在资源受限的设备或超高速通信中。

此外，大多数纠错码是为处理“比特翻转”而设计的——即0变为1或1变为0。涉及比特插入或删除的错误在异步数据流中更为常见，要高效地纠正这些错误要困难得多，通常需要不同的编码方案或额外的同步机制。

光盘上的划痕或遥远信号中的宇宙射线影响不再是致命的缺陷。相反，它们是被优雅的数学盾牌平滑的短暂波动，默默地确保了我们数字宇宙的完整性。

Una tenue susurro de datos, enviado a través de miles de millones de kilómetros desde el borde de nuestro sistema solar, llega a la Tierra con cada bit intacto. O el familiar zumbido de un disco compacto, reproduciéndose perfectamente a pesar de las marcas visibles. Ambos dependen de una capa invisible de redundancia minuciosa.

Este milagro silencioso, la detección y corrección de errores en información transmitida o almacenada, sustenta gran parte de nuestro mundo digital. Es un campo nacido de la frustración e intuición matemática, arraigado en la comprensión de que el ruido e imperfección son inherentes a cada canal de comunicación. En lugar de simplemente señalar errores y exigir una retransmisión – una hazaña imposible para sondas espaciales profundas o una simple inconveniencia para medios cotidianos – los códigos correctores de errores construyen resiliencia directamente en el mensaje mismo.

El concepto fundamental es sencillo: agregar información adicional estructurada cuidadosamente a los datos originales. Esta redundancia permite a un receptor no solo identificar dónde ocurrió la corrupción, sino a menudo reconstruir los datos originales, indemnes, sin necesidad de pedir una retransmisión. El costo es el ancho de banda, un volumen mayor de bits enviados que estrictamente necesario para el mensaje original, pero la recompensa es la fiabilidad, incluso en los entornos más hostiles.

La intuición de Hamming y el nacimiento de la paridad La historia de la corrección de errores moderna comienza a finales de la década de 1940, en los santuarios de [[Bell Labs]]. [[Richard Hamming]], un matemático que trabajaba con máquinas de computación tempranas, se enfadaba cada vez más por las frecuentes caídas causadas por errores de bit único en lectores de tarjetas perforadas. Estas máquinas se detenían, volcaban su memoria y lo obligaban a reiniciar sus cálculos, a menudo durante el fin de semana. La solución de sus colegas era agregar un solo [[parity bit]] a cada bloque de datos – un bit extra que simplemente indicaba si la cantidad de '1's en el bloque era par o impar. Esto permitía la detección de errores, pero no su corrección. Si se encontraba un error, la máquina simplemente se detenía.

Hamming se dio cuenta de que si uno pudiera determinar *cuál* bit estaba en error, en lugar de simplemente *que* existía un error, entonces la corrección se hacía posible. En 1950, publicó su obra seminal introduciendo los códigos Hamming, la primera familia de códigos correctores de errores capaces de identificar y corregir errores de bit único. Su avance fue codificar información de manera que la posición de cualquier error único pudiera determinarse de forma única a partir de un conjunto de comprobaciones de paridad calculadas. Fue un paso fundamental, superando la simple detección de errores para pasar a una reparación proactiva.

El caballo de batalla: Códigos Reed-Solomon Aunque los códigos Hamming resultaron valiosos para ciertas aplicaciones, el mundo real a menudo presenta más de solo errores de bit único. Los errores de ráfaga – donde varios bits consecutivos se corrompen – son comunes en medios físicos como CDs rayados o canales de radio ruidosos. Para estos escenarios, se necesitaban códigos más robustos. Entraron en escena los [[Reed-Solomon code]]s, concebidos por primera vez en 1960 por Irving Reed y Gustave Solomon. Estos códigos de bloque operan sobre símbolos (grupos de bits) en lugar de bits individuales, lo que los hace excepcionalmente buenos para manejar errores de ráfaga.

Los códigos Reed-Solomon logran esto al tratar los datos como polinomios sobre campos finitos. El codificador evalúa este polinomio en varios puntos, y estos puntos evaluados, junto con los datos originales, se transmiten. El receptor puede entonces reconstruir el polinomio original incluso si algunos puntos se pierden o se corrompen, de manera similar a determinar una curva a partir de algunos puntos conocidos. Esta elegancia matemática los hizo omnipresentes. Son la columna vertebral de la audio digital (CDs), video (DVDs, Blu-ray), códigos QR y son críticos para las comunicaciones espaciales profundas, donde las señales son débiles y la interferencia es constante.

Alcanzando el límite de Shannon El límite teórico de la comunicación confiable sobre un canal ruidoso fue establecido por [[Claude Shannon]] en 1948 con su teorema de codificación de canales ruidosos. El trabajo de Shannon reveló que hay una tasa máxima a la cual la información puede transmitirse con una probabilidad de error arbitrariamente pequeña, incluso en presencia de ruido. Durante décadas, ingenieros y matemáticos trabajaron para desarrollar códigos que pudieran acercarse a este límite teórico [[Shannon limit]].

Los códigos correctores de errores modernos, como los Códigos Turbo (introducidos a principios de la década de 1990) y los LDPC codes (inicialmente propuestos por Robert Gallager en 1960 pero en gran medida ignorados hasta finales de la década de 1990 debido a la complejidad computacional), han hecho un progreso notable. Estos códigos emplean algoritmos de decodificación iterativa que intercambian información entre múltiples decodificadores más simples, mejorando gradualmente la probabilidad de decodificación correcta. En particular, los códigos LDPC son ahora centrales para estándares de comunicación de alta velocidad como DVB-S2 (televisión digital), WiMAX y 10GBase-T Ethernet, ampliando los límites de lo posible en entornos ruidosos.

Lo que aún no sabemos

Aunque los códigos pueden acercarse al límite de Shannon para modelos específicos de canales, los canales del mundo real rara vez se comprenden perfectamente o son estáticos. Adaptar la corrección de errores dinámicamente a condiciones cambiantes de ruido sigue siendo un desafío complejo.

La sobrecarga computacional para decodificar estos códigos avanzados, aunque significativamente reducida, sigue siendo considerable. Encontrar maneras de lograr un rendimiento cercano al óptimo con menos potencia computacional es un área de investigación en curso, especialmente para dispositivos con recursos limitados o comunicaciones de ultravelocidad.

Además, la mayoría de los códigos correctores de errores están diseñados para manejar 'volteos de bit' – donde un 0 se convierte en un 1 o viceversa. Los errores que involucran inserciones o eliminaciones de bits, comunes en flujos de datos asincrónicos, son mucho más difíciles de corregir eficientemente, a menudo requiriendo esquemas de codificación diferentes o mecanismos adicionales de sincronización.

Un arañazo en un disco o el impacto de una radiación cósmica en una señal distante ya no son fallos fatales. En su lugar, son destellos momentáneos suavizados por un escudo matemático elegante, asegurando silenciosamente la integridad de nuestro universo digital.

Um sussurro ténue de dados, enviado através de bilhões de quilómetros desde a borda do nosso sistema solar, alcança a Terra com cada bit intacto. Ou o conhecido zumbido de um disco compacto, a tocar perfeitamente apesar das arranhaduras visíveis. Ambos dependem de uma camada invisível de redundância minuciosa.

Este milagre silencioso, a detecção e correção de erros em informações transmitidas ou armazenadas, sustenta boa parte do nosso mundo digital. É um campo nascido da frustração e da intuição matemática, enraizado na compreensão de que o ruído e a imperfeição são inerentes a cada canal de comunicação. Em vez de simplesmente sinalizar erros e exigir uma nova transmissão – um feito impossível para sondas espaciais profundas ou uma inconveniência trivial para meios de comunicação cotidianos – códigos corretores de erro constroem resiliência diretamente na própria mensagem.

O conceito fundamental é simples: adicionar informação extra cuidadosamente estruturada aos dados originais. Essa redundância permite que um receptor não apenas localize onde a corrupção ocorreu, mas, muitas vezes, reconstrua os dados originais, imaculados, sem precisar pedir uma nova transmissão. O custo é a largura de banda, um volume maior de bits enviados do que estritamente necessário para a mensagem original, mas a recompensa é a confiabilidade, mesmo nos ambientes mais hostis.

A Intuição de Hamming e o Nascimento da Paridade A história da correção moderna de erros começa no final dos anos 1940, nas sagradas salas de [[Bell Labs]]. [[Richard Hamming]], um matemático que trabalhava com máquinas de computação primitivas, ficava cada vez mais irritado com os frequentes travamentos causados por erros em cartões perfurados. Essas máquinas paravam, descarregavam a memória e obrigavam-no a reiniciar seus cálculos, muitas vezes durante o fim de semana. A solução dos colegas era adicionar uma única [[parity bit]] a cada bloco de dados – um bit extra que simplesmente indicava se o número de '1's no bloco era par ou ímpar. Isso permitia a detecção de erros, mas não a correção. Se um erro fosse encontrado, a máquina simplesmente parava.

Hamming percebeu que, se fosse possível determinar *qual* bit estava com erro, em vez de apenas *que* um erro existia, então a correção tornar-se-ia possível. Em 1950, ele publicou seu trabalho seminal introduzindo os códigos Hamming, a primeira família de códigos corretores de erro capazes de identificar e corrigir erros em um único bit. Sua quebra de paradigma foi codificar informações de tal forma que a posição de qualquer erro único pudesse ser determinada de forma única a partir de um conjunto de verificações de paridade calculadas. Foi um passo fundamental, ultrapassando a detecção simples de erros para a correção proativa.

O Cavalo de Batalha: Códigos Reed-Solomon Embora os códigos Hamming se mostrassem valiosos para certas aplicações, o mundo real frequentemente apresenta mais do que apenas erros em um único bit. Erros em sequência – onde vários bits consecutivos são corrompidos – são comuns em mídias físicas como CDs riscados ou canais de rádio ruidosos. Para esses cenários, eram necessários códigos mais robustos. Entram os [[Reed-Solomon code]]s, concebidos pela primeira vez em 1960 por Irving Reed e Gustave Solomon. Esses códigos em blocos operam em símbolos (grupos de bits) em vez de bits individuais, tornando-os excepcionalmente bons na lidar com erros em sequência.

Os códigos Reed-Solomon conseguem isso tratando os dados como polinômios sobre campos finitos. O codificador avalia esse polinômio em vários pontos, e esses pontos avaliados, junto com os dados originais, são transmitidos. O receptor pode então reconstruir o polinômio original mesmo que alguns pontos estejam perdidos ou corrompidos, muito como determinar uma curva a partir de alguns pontos conhecidos. Essa elegância matemática tornou-os ubíquos. São a base da áudio digital (CDs), vídeo (DVDs, Blu-ray), códigos QR e são críticos para comunicações espaciais profundas, onde os sinais são fracos e a interferência é constante.

Chegando ao Limite de Shannon O limite teórico da comunicação confiável em um canal ruidoso foi estabelecido por [[Claude Shannon]] em 1948 com seu teorema de codificação de canais ruidosos. O trabalho de Shannon revelou que existe uma taxa máxima na qual as informações podem ser transmitidas com uma probabilidade de erro arbitrariamente pequena, mesmo na presença de ruído. Durante décadas, engenheiros e matemáticos trabalharam para desenvolver códigos que pudessem se aproximar desse limite teórico [[Shannon limit]].

Códigos modernos de correção de erros, como os Códigos Turbo (introduzidos no início dos anos 1990) e os LDPC codes (inicialmente propostos por Robert Gallager em 1960, mas amplamente ignorados até o final dos anos 1990 devido à complexidade computacional), fizeram progressos notáveis. Esses códigos utilizam algoritmos de decodificação iterativa que trocam informações entre vários decodificadores mais simples, gradualmente aumentando a probabilidade de decodificação correta. Em particular, os códigos LDPC são agora centrais para padrões de comunicação de alta velocidade como DVB-S2 (televisão digital), WiMAX e 10GBase-T Ethernet, impulsionando os limites do que é possível em ambientes ruidosos.

O que ainda não sabemos

Embora códigos possam se aproximar do limite de Shannon para modelos específicos de canais, canais reais raramente são perfeitamente compreendidos ou estáticos. Adaptar a correção de erros dinamicamente às condições de ruído em mudança permanece um desafio complexo.

A sobrecarga computacional para decodificar esses códigos avançados, embora significativamente reduzida, ainda é considerável. Encontrar formas de alcançar desempenho próximo ao ideal com menos poder computacional é uma área de pesquisa contínua, especialmente para dispositivos com recursos limitados ou comunicação de ultravelocidade.

Além disso, a maioria dos códigos corretores de erro é projetada para lidar com "inversões de bit" – onde um 0 vira 1 ou vice-versa. Erros envolvendo inserções ou exclusões de bits, comuns em fluxos de dados assíncronos, são muito mais difíceis de corrigir com eficiência, muitas vezes exigindo esquemas de codificação diferentes ou mecanismos adicionais de sincronização.

Um arranhão em um disco ou um impacto de raio cósmico em um sinal distante não são mais falhas fatais. Em vez disso, são apenas pequenas interrupções suavizadas por um escudo matemático elegante, garantindo silenciosamente a integridade do nosso universo digital.

Une légère murmure de données, envoyé à travers des milliards de kilomètres depuis la limite de notre système solaire, atteint la Terre avec chaque bit intact. Ou le bruissement familier d'un disque compact, jouant parfaitement malgré des rayures visibles. Les deux s'appuient sur une couche invisible de redondance méticuleuse.

Ce miracle silencieux, la détection et la correction des erreurs dans les informations transmises ou stockées, est à la base de notre monde numérique. Ce domaine est né de la frustration et d'une intuition mathématique, ancré dans la compréhension que le bruit et l'imperfection sont inhérents à chaque canal de communication. Au lieu de simplement signaler les erreurs et de demander une retransmission – une prouesse impossible pour les sondes interplanétaires ou une simple gêne pour les médias courants – les codes correcteurs d'erreurs construisent directement une résilience dans le message lui-même.

L'idée fondamentale est simple : ajouter à l'information originale une donnée supplémentaire soigneusement structurée. Cette redondance permet au récepteur non seulement d'identifier où la corruption s'est produite, mais souvent de reconstituer les données originales intactes, sans avoir à demander de retransmission. Le prix à payer est la bande passante, un volume plus important de bits envoyés que nécessaire pour le message d'origine, mais le bénéfice est la fiabilité, même dans les environnements les plus hostiles.

L'apport de Hamming et la naissance de la parité L'histoire de la correction d'erreurs moderne commence à la fin des années 1940, dans les salles sacrées de [[Bell Labs]]. [[Richard Hamming]], un mathématicien travaillant sur des machines de calcul précoce, s'irritait de plus en plus des plantages fréquents causés par des erreurs de bits uniques dans les lecteurs de cartes perforées. Ces machines s'arrêtaient, vidaient leur mémoire, et l'obligeaient à relancer ses calculs, souvent pendant le week-end. La solution proposée par ses collègues était d'ajouter un seul [[parity bit]] à chaque bloc de données – un bit supplémentaire indiquant simplement si le nombre de '1' dans le bloc était pair ou impair. Cela permettait de détecter les erreurs, mais pas de les corriger. Si une erreur était détectée, la machine s'arrêtait simplement.

Hamming réalisa que si l'on pouvait déterminer *quelle* bit était erronée, plutôt que simplement *qu'une* erreur existait, alors la correction devenait possible. En 1950, il publia son œuvre fondamentale introduisant les codes de Hamming, la première famille de codes correcteurs d'erreurs capables d'identifier et de corriger les erreurs de bits uniques. Sa percée fut d'encoder l'information de telle sorte que la position d'une erreur unique pût être déterminée de façon unique à partir d'un ensemble de vérifications de parité calculées. C'était une étape fondamentale, dépassant la simple détection d'erreurs pour permettre une réparation proactive.

La cheville ouvrière : les codes de Reed-Solomon Alors que les codes de Hamming s'avérèrent précieux pour certaines applications, le monde réel génère souvent plus que des erreurs de bits uniques. Les erreurs par vagues – où plusieurs bits consécutifs sont corrompus – sont fréquentes dans les supports physiques comme les CD rayés ou les canaux radio bruyants. Pour ces scénarios, des codes plus robustes étaient nécessaires. Entrent en jeu les [[Reed-Solomon code]]s, conçus pour la première fois en 1960 par Irving Reed et Gustave Solomon. Ces codes par blocs travaillent sur des symboles (groupes de bits) plutôt que sur les bits individuels, ce qui les rend particulièrement efficaces pour gérer les erreurs par vagues.

Les codes de Reed-Solomon y parviennent en traitant les données comme des polynômes sur des corps finis. Le codeur évalue ce polynôme à plusieurs points, et ces points évalués, ainsi que les données originales, sont transmis. Le récepteur peut alors reconstituer le polynôme original même si certains points sont perdus ou corrompus, tout comme déterminer une courbe à partir de quelques points connus. Cette élégance mathématique les rendit ubiquistes. Ils sont le pilier de l'audio numérique (CD), de la vidéo (DVD, Blu-ray), des codes QR, et sont cruciaux pour les communications interplanétaires, où les signaux sont faibles et l'interférence constante.

En quête de la limite de Shannon La limite théorique de la communication fiable sur un canal bruyant a été établie par [[Claude Shannon]] en 1948 avec son théorème de codage de canal bruyant. Le travail de Shannon révélait qu'il existe un taux maximal auquel l'information peut être transmise avec une probabilité d'erreur arbitrairement faible, même en présence de bruit. Pendant des décennies, ingénieurs et mathématiciens ont travaillé à développer des codes capables d'approcher cette limite théorique [[Shannon limit]].

Les codes correcteurs d'erreurs modernes, tels que les codes Turbo (introduits au début des années 1990) et les LDPC codes (initialement proposés par Robert Gallager en 1960 mais largement négligés jusqu'à la fin des années 1990 en raison de leur complexité computationnelle), ont fait des progrès remarquables. Ces codes utilisent des algorithmes de décodage itératifs qui échangent des informations entre plusieurs décodeurs simples, améliorant progressivement la probabilité de décodage correct. Les codes LDPC, en particulier, sont désormais au cœur des normes de communication à haut débit comme DVB-S2 (télévision numérique), WiMAX et 10GBase-T Ethernet, poussant les limites de ce qui est possible dans les environnements bruyants.

Ce que nous ne savons toujours pas

Alors que les codes peuvent s'approcher de la limite de Shannon pour certains modèles de canaux, les canaux réels sont rarement parfaitement compris ou statiques. Adapter dynamiquement la correction d'erreurs aux conditions changeantes du bruit reste un défi complexe.

L'overhead computationnel nécessaire au décodage de ces codes avancés, bien que considérablement réduit, reste encore important. Trouver des moyens d'atteindre une performance proche de l'optimum avec moins de puissance de calcul est un domaine de recherche en cours, particulièrement pour les appareils à faible ressource ou les communications à ultra-haute vitesse.

De plus, la plupart des codes correcteurs d'erreurs sont conçus pour gérer les « basculements de bits » – où un 0 devient un 1 ou vice-versa. Les erreurs impliquant des insertions ou des suppressions de bits, fréquentes dans les flux de données asynchrones, sont bien plus difficiles à corriger efficacement, souvent nécessitant des schémas de codage différents ou des mécanismes supplémentaires de synchronisation.

Une rayure sur un disque ou l'impact d'un rayon cosmique sur un signal lointain ne sont plus des défauts mortels. Au contraire, ce sont des perturbations momentanées atténuées par un bouclier mathématique élégant, assurant silencieusement l'intégrité de notre univers numérique.

数十億キロメートルの距離を越えて、太陽系の果てから送られてくる僅かなデータのささやきが、ビット一つとして欠けずに地球に届く。あるいは、傷だらけのコンパクト・ディスクが、見事に音を奏でるあの馴染み深い唸り声。これらはどちらも、目に見えない精緻な冗長性の上に成り立っている。

この静かな奇跡である、送信または保存された情報の誤りを検出・修正する仕組みは、私たちのデジタル世界の多くを支える基盤です。これは、苛立ちと数学的洞察の産物である分野で、すべての通信チャネルにノイズと不完全さが含まれているという理解に根ざしています。単に誤りをマークして再送信を求めるだけではなく——これは深宇宙探査機には不可能であり、日常的なメディアにとっては些細な不便に過ぎません——誤り訂正符号は、メッセージそのものに頑健性を直接組み込むものです。

基本的な概念は単純です。元のデータに、丁寧に構造化された追加情報を付加するのです。この冗長性により、受信側は情報の破損がどこで起きたかを特定するだけでなく、再送を要求することなく、しばしば元の無傷のデータを再構成することができます。その代償は帯域幅であり、元のメッセージには厳密には必要でないより多くのビットを送る必要がありますが、その見返りは、最も過酷な環境でも信頼性を確保することです。

ハミングの洞察とパリティの誕生現代的な誤り訂正の物語は1940年代後半、[[Bell Labs]]の聖域とも言える廊下で始まります。[[Richard Hamming]]という数学者は、初期のコンピュータ機械と仕事をしていたのですが、パンチカードリーダーの1ビット誤りによる頻繁なクラッシュにますます苛立ちを感じていました。これらの機械は停止し、メモリをダンプし、彼は計算をやり直さざるを得なかったのです。彼の同僚たちの解決策は、各データブロックに単一の[[parity bit]]を追加することでした——これは単にブロック内の「1」の数が偶数か奇数かを示す追加ビットです。これにより誤りを検出することは可能でしたが、訂正はできませんでした。誤りが見つかると、単に機械が停止するだけでした。

ハミングは、単に「誤りがある」ということではなく、「どのビットが誤っているか」を特定できれば、訂正が可能になると気付きました。1950年、彼は単一ビット誤りを識別・修正できる最初の誤り訂正符号ファミリーであるハミング符号を導入した画期的な論文を発表しました。彼の突破点は、情報を符号化して、任意の単一誤りの位置が一意に決定できるようにすることでした。これは単なる誤り検出を超えて、能動的な誤り修正への重要な第一歩でした。

主役：リード・ソロモン符号ハミング符号は特定の用途では非常に有用でしたが、現実世界では単一ビット誤り以上の問題が頻繁に起こります。バースト誤り——いくつかの連続したビットが破損するもの——は、傷ついたCDやノイジーな無線チャネルなどの物理媒体でよく見られます。こうしたシナリオには、より頑健な符号が必要でした。それが[[Reed-Solomon code]]であり、1960年にアーヴィング・リードとガストーブ・ソロモンによって最初に考案されました。これらのブロック符号は個々のビットではなく、ビットのグループである「シンボル」を扱うため、バースト誤りを非常に効果的に処理できます。

リード・ソロモン符号は、データを有限体上の多項式として扱うことでこれを達成します。エンコーダーはこの多項式をいくつかの点で評価し、これらの評価された点と元のデータを送信します。受信側は、いくつかの点が失われたり破損したりしていても、元の多項式を再構成できます。これは、いくつかの既知の点から曲線を決定するのと似ています。この数学的洗練さにより、リード・ソロモン符号は汎用的になりました。デジタルオーディオ（CD）、ビデオ（DVD、ブルーレイ）、QRコードの基盤であり、信号が弱く干渉が常に存在する深宇宙通信においても不可欠です。

シャノン限界への挑戦ノイジーなチャネルにおける信頼性ある通信の理論的限界は、[[Claude Shannon]]が1948年に彼のノイジー・チャネル・コーディング定理で確立しました。シャノンの研究は、ノイズが存在する中でも、情報が任意に小さな誤り確率で送信できる最大速度があることを明らかにしました。何十年もの間、エンジニアと数学者たちは、この理論的[[Shannon limit]]に迫る符号の開発に苦労しました。

現代の誤り訂正符号、たとえば1990年代初頭に導入されたターボ符号や、1960年にRobert Gallagerによって最初に提案され、計算の複雑さのため1990年代後半までほとんど注目されなかったLDPC codeは、画期的な進展を遂げています。これらの符号は、複数の単純なデコーダー間で情報をやり取りする反復デコードアルゴリズムを使用し、正しいデコードの確率を徐々に高めていきます。特にLDPC符号は、DVB-S2（デジタルテレビジョン）、WiMAX、10GBase-Tイーサネットなどの高速通信規格において中心的役割を果たしており、ノイジーな環境での可能性の境界を押し広げています。

まだわかっていないこと

特定のチャネルモデルでは符号がシャノン限界に近づけるものの、現実のチャネルはほとんど完全に理解されたり静的であるとは限りません。ノイズ条件の変化に動的に誤り訂正を適応させるのは依然として複雑な課題です。

これらの高度な符号のデコードに必要な計算オーバーヘッドは大幅に減少していますが、依然としてかなりのものです。少ない計算能力でほぼ最適な性能を達成する方法を見つけることは、リソースが限られたデバイスや超高速通信において特に重要な研究分野です。

さらに、ほとんどの誤り訂正符号は「ビット反転」——0が1になり、またはその逆になる誤り——を処理するように設計されています。非同期データストリームで一般的なビットの挿入または削除を伴う誤りは、効率的に修正するのがはるかに難しいため、異なる符号方式や追加の同期メカニズムが必要となることが多いです。

ディスクの傷や遠くの信号に影響を与える宇宙線は、もはや致命的な欠陥ではありません。それらは、洗練された数学的シールドによって、デジタル宇宙の整合性を静かに保証する一時的なノイズに過ぎません。

Sebuah bisikan data yang samar, dikirim melalui miliaran kilometer dari ujung sistem tata surya kita, mencapai Bumi dengan setiap bitnya utuh. Atau suara berputar yang akrab dari sebuah cakram padat, diputar sempurna meskipun terdapat goresan yang terlihat. Keduanya bergantung pada lapisan redundansi yang teliti dan tak terlihat.

Ajaib diam ini, deteksi dan koreksi kesalahan dalam informasi yang dikirim atau disimpan, menjadi dasar bagi dunia digital kita. Ini adalah bidang yang lahir dari frustrasi dan wawasan matematis, berakar pada pemahaman bahwa kebisingan dan ketidaksempurnaan adalah bagian alami dari setiap saluran komunikasi. Alih-alih hanya menandai kesalahan dan meminta pengiriman ulang—yang mustahil dilakukan untuk probe luar angkasa atau bahkan gangguan sepele untuk media sehari-hari—kode koreksi kesalahan membangun ketahanan langsung ke dalam pesan itu sendiri.

Konsep dasarnya sederhana: tambahkan informasi tambahan yang terstruktur secara hati-hati ke data asli. Redundansi ini memungkinkan penerima tidak hanya mengenali di mana terjadi kerusakan, tetapi seringkali merekonstruksi data asli tanpa cacat, tanpa perlu meminta pengiriman ulang. Biayanya adalah lebar pita, volume bit yang dikirim lebih besar dari yang sebenarnya diperlukan untuk pesan asli, tetapi imbalannya adalah keandalan, bahkan dalam lingkungan paling keras sekalipun.

Wawasan Hamming dan Lahirnya Paritas Kisah koreksi kesalahan modern dimulai di akhir tahun 1940-an, di aula megah [[Bell Labs]]. [[Richard Hamming]], seorang matematikawan yang bekerja dengan mesin komputasi awal, semakin kesal dengan kecelakaan yang sering terjadi akibat kesalahan satu bit pada pembaca kartu lubang. Mesin-mesin ini akan berhenti, membuang memori mereka, dan memaksanya memulai ulang perhitungan, seringkali di akhir pekan. Solusi rekan-rekannya adalah menambahkan satu [[parity bit]] ke setiap blok data—sebuah bit tambahan yang hanya menunjukkan apakah jumlah '1' dalam blok tersebut genap atau ganjil. Ini memungkinkan deteksi kesalahan, tetapi tidak koreksi. Jika ditemukan kesalahan, mesin hanya berhenti.

Hamming menyadari bahwa jika seseorang dapat menentukan *bit mana* yang bermasalah, bukan hanya *ada kesalahan*, maka koreksi menjadi mungkin. Pada tahun 1950, ia mempublikasikan karyanya yang luar biasa, memperkenalkan kode Hamming, keluarga pertama kode koreksi kesalahan yang mampu mengidentifikasi dan memperbaiki kesalahan satu bit. Terobosannya adalah mengkodekan informasi sedemikian rupa sehingga posisi kesalahan tunggal dapat ditentukan secara unik dari serangkaian pemeriksaan paritas yang dihitung. Ini adalah langkah dasar, melangkah lebih jauh dari deteksi kesalahan sederhana ke perbaikan proaktif.

Kuda Bekerja: Kode Reed-Solomon Meskipun kode Hamming terbukti sangat berguna untuk beberapa aplikasi, dunia nyata seringkali menghadirkan lebih dari hanya kesalahan satu bit. Kesalahan burst—di mana beberapa bit berturut-turut rusak—umum terjadi pada media fisik seperti CD yang tergores atau saluran radio yang bising. Untuk skenario ini, diperlukan kode yang lebih kuat. Masuklah [[Reed-Solomon code]]s, yang pertama kali dipikirkan pada tahun 1960 oleh Irving Reed dan Gustave Solomon. Kode blok ini bekerja pada simbol (kelompok bit) bukan pada bit individual, menjadikannya sangat baik dalam menangani kesalahan burst.

Kode Reed-Solomon mencapai hal ini dengan memperlakukan data sebagai polinomial di bidang hingga. Pengkode mengevaluasi polinomial ini di beberapa titik, dan titik-titik yang dievaluasi tersebut, bersama dengan data asli, dikirim. Penerima kemudian dapat merekonstruksi polinomial asli bahkan jika beberapa titik hilang atau rusak, mirip dengan menentukan kurva dari beberapa titik yang diketahui. Elegansi matematis ini membuat mereka menjadi sangat umum. Mereka adalah tulang punggung audio digital (CD), video (DVD, Blu-ray), kode QR, dan menjadi kritis untuk komunikasi luar angkasa, di mana sinyal lemah dan gangguan konstan.

Menuju Batas Shannon Batas teoretis komunikasi yang dapat diandalkan melalui saluran bising ditetapkan oleh [[Claude Shannon]] pada tahun 1948 melalui teorema coding saluran bisingnya. Karya Shannon mengungkapkan bahwa ada tingkat maksimum di mana informasi dapat dikirim dengan probabilitas kesalahan yang semakin kecil, bahkan dalam kehadiran kebisingan. Selama bertahun-tahun, para insinyur dan matematikawan berusaha mengembangkan kode yang dapat mendekati batas teoretis [[Shannon limit]] ini.

Kode koreksi kesalahan modern, seperti Turbo Codes (diperkenalkan pada awal tahun 1990-an) dan LDPC codes (yang awalnya diproposikan oleh Robert Gallager pada tahun 1960 tetapi diabaikan hingga akhir tahun 1990-an karena kompleksitas komputasi), telah membuat kemajuan luar biasa. Kode-kode ini menggunakan algoritma dekoding iteratif yang bertukar informasi antara beberapa dekoder sederhana, secara bertahap meningkatkan kemungkinan dekoding yang benar. Khususnya, kode LDPC kini menjadi inti dari standar komunikasi berkecepatan tinggi seperti DVB-S2 (televisi digital), WiMAX, dan 10GBase-T Ethernet, memperluas batas-batas yang mungkin dalam lingkungan bising.

Apa yang Masih Kita Tidak Tahu

Meskipun kode dapat mendekati batas Shannon untuk model saluran tertentu, saluran dunia nyata jarang dipahami secara sempurna atau statis. Menyesuaikan koreksi kesalahan secara dinamis terhadap perubahan kondisi kebisingan tetap menjadi tantangan yang kompleks.

Overhead komputasi untuk mendekode kode canggih ini, meskipun telah berkurang secara signifikan, tetap cukup besar. Mencari cara untuk mencapai kinerja optimal dengan daya komputasi yang lebih sedikit adalah bidang penelitian yang terus berlangsung, terutama untuk perangkat dengan sumber daya terbatas atau komunikasi berkecepatan ultra-tinggi.

Selain itu, sebagian besar kode koreksi kesalahan dirancang untuk menangani 'pembalik bit'—di mana 0 berubah menjadi 1 atau sebaliknya. Kesalahan yang melibatkan penambahan atau penghapusan bit, umum terjadi dalam aliran data asinkron, jauh lebih sulit diperbaiki secara efisien, sering memerlukan skema coding yang berbeda atau mekanisme sinkronisasi tambahan.

Goresan pada piringan atau dampak sinar kosmik pada sinyal jarak jauh bukan lagi kegagalan fatal. Alih-alih, mereka hanya gangguan singkat yang dihaluskan oleh benteng matematis yang elegan, secara diam-diam memastikan integritas alam digital kita.

هُمسةٌ خافتةٌ من البيانات، تُرسَل عبر مليارات الكيلومترات من حافة نظامنا الشمسي، تصل إلى الأرض بجميع بتاتها سليمة. أو صوت مألوف لمفتاح قرص مدمج، يُعزف بسلاسةٍ رغم وجود خدوشٍ ظاهرةٍ عليه. وكلا الأمرين يعتمدان على طبقةٍ غير مرئيةٍ من التكرار الدقيق.

هذا العَجَب الهادئ، اكتشاف وتصحيح الأخطاء في المعلومات المُرسلة أو المخزنة، هو أساسٌ للكثير من عالمنا الرقمي. إنها حقل نشأ من الإحباط والرؤية الرياضية، مُرتكز على فهمٍ بأن الضوضاء وعدم الكمال جزء من كل قناة اتصال. بدلًا من الإشارة إلى الأخطاء فقط والطلب إعادة الإرسال - وهو أمر مستحيل بالنسبة للمنصات الفضائية العميقة أو حتى مشكلة بسيطة بالنسبة للوسائط اليومية - فإن رموز تصحيح الأخطاء تبني المقاومة مباشرةً داخل الرسالة نفسها.

المفهوم الأساسي بسيط: إضافة معلومات إضافية مُنظمة بعناية إلى البيانات الأصلية. تسمح هذه الفائضية المستقبل بالتحديد ليس فقط أين حدثت التلفيات، بل غالبًا إعادة بناء البيانات الأصلية دون عيوب، دون الحاجة إلى طلب إعادة الإرسال. والتكلفة هي عرض النطاق الترددي، أي كمية أكبر من البتات المرسلة مما هو ضروري فعليًا للرسالة الأصلية، لكن المكاسب هي الموثوقية، حتى في البيئات الأكثر قسوة.

رؤية هامينغ وميلاد التكافؤ تبدأ قصة تصحيح الأخطاء الحديثة في أواخر الأربعينيات من القرن العشرين، في قاعات [[Bell Labs]] المقدسة. [[Richard Hamming]]، عالم رياضيات يعمل مع أجهزة الحواسيب المبكرة، كان يشعر بالإحباط المتزايد بسبب التوقفات المتكررة الناتجة عن أخطاء بت واحدة في قارئات البطاقات المثقبة. كانت هذه الأجهزة تتوقف، وتفرغ ذاكرتها، وتجبره على إعادة حساباته، غالبًا خلال عطلة نهاية الأسبوع. كانت الحلول التي اقترحها زملاؤه هي إضافة بت [[parity bit]] واحد لكل كتلة من البيانات - بت إضافي يشير فقط إلى ما إذا كانت عدد البتات "1" في الكتلة زوجيًا أو فرديًا. سمح ذلك باكتشاف الأخطاء، لكنه لم يسمح بتصحيحها. إذا وُجد خطأ، توقفت الآلة.

أدرك هامينغ أنه إذا كان بالإمكان تحديد *أي* بت هو الخطأ، وليس فقط *وجود* خطأ، فإن التصحيح أصبح ممكنًا. في عام 1950، نشر عمله المركزي الذي قدم فيه رموز هامينغ، أول عائلة من رموز تصحيح الأخطاء قادرة على تحديد وإصلاح أخطاء بت واحدة. كانت مفتاحه هو تشفير المعلومات بحيث يمكن تحديد موقع أي خطأ فردي بشكل فريد من خلال مجموعة من التحقق من التكافؤ المحسوب. كانت خطوة أساسية، تجاوزت اكتشاف الأخطاء البسيطة إلى إصلاح الأخطاء بشكل إيجابي.

العمود الفقري: رموز ريد-سولومان بينما أثبتت رموز هامينغ فائدتها في بعض التطبيقات، فإن العالم الحقيقي غالبًا ما يطرح أكثر من أخطاء بت واحدة. أخطاء تفريعيّة - حيث تُتلف عدة بتات متتالية - شائعة في الوسائط الفيزيائية مثل الأقراص المضغوطة المخدوشة أو قنوات الراديو الضوضائية. بالنسبة لهذه الحالات، كانت هناك حاجة إلى رموز أكثر صلابة. ها هي [[Reed-Solomon code]]s، التي تم تصورها لأول مرة في عام 1960 بواسطة إيرفيغ ريد وغستاف سولومان. تعمل هذه الرموز الكتلة على رموز (مجموعات من البتات) بدلًا من البتات الفردية، مما يجعلها ممتازة بشكل خاص في التعامل مع الأخطاء التفريعيّة.

تتحقق رموز ريد-سولومان من ذلك من خلال معاملة البيانات كمتعددة حدود على الحقول المنتهية. يقوم المُشفِّر بتقييم هذه المتعددة الحدود في عدة نقاط، ويتم إرسال هذه النقاط المُقيَّمة مع البيانات الأصلية. يمكن للمستلم بعد ذلك إعادة بناء المتعددة الحدود الأصلية حتى لو فقدت أو تلفت بعض النقاط، تمامًا كما يمكن تحديد منحنى من نقاط معروفة. جعل هذا الأناقة الرياضية هذه الرموز شائعة جدًا. إنها العمود الفقري للصوتيات الرقمية (الأقراص المضغوطة)، والفيديو (الأقراص المدمجة، الأقراص المضغوطة الفائقة الجودة)، والرموز QR، وهي حاسمة في الاتصالات الفضائية العميقة، حيث تكون الإشارات ضعيفة والتشويش مستمر.

الوصول إلى حد شانون تم تحديد حد النقل الموثوق عبر قناة ضوضائية من قبل [[Claude Shannon]] في عام 1948 من خلال نظريته في تشفير القنوات الضوضائية. كشفت أعمال شانون أن هناك سرعة قصوى يمكن من خلالها نقل المعلومات بفرصة خطأ تعسفي صغيرة، حتى في وجود ضوضاء. لعقود، عمل المهندسون والرياضياتيون على تطوير رموز تقترب من هذا الحد النظري [[Shannon limit]].

الرموز الحديثة لتصحيح الأخطاء، مثل رموز Turbo (تم تقديمه في أوائل التسعينيات) ورموز LDPC code (تم اقتراحها لأول مرة من قبل Robert Gallager في عام 1960 ولكن تم تجاهلها بشكل كبير حتى أواخر التسعينيات بسبب التعقيد الحاسوبي)، حققت تقدمًا ملحوظًا. تستخدم هذه الرموز خوارزميات تفكير تكرارية تتبادل المعلومات بين عدة تفكيرات بسيطة، مما يحسن تدريجيًا احتمالية التفكير الصحيح. تُعتبر رموز LDPC الآن جوهرية في معايير الاتصالات عالية السرعة مثل DVB-S2 (التلفزيون الرقمي)، وWiMAX، وEthernet 10GBase-T، وتنسج الحدود لما هو ممكن في البيئات الضوضائية.

ما لا نزال لا نعرفه

بينما يمكن للرموز الاقتراب من حد شانون لبعض نماذج القنوات، فإن القنوات الواقعية نادراً ما تُفهم تمامًا أو تكون ثابتة. التكيف مع تصحيح الأخطاء ديناميكيًا مع ظروف الضوضاء المتغيرة لا يزال تحديًا معقدًا.

التكاليف الحاسوبية لفك تشفير هذه الرموز المتقدمة، رغم تقليلها بشكل كبير، لا تزال كبيرة. العثور على طرق لتحقيق الأداء المثالي تقريبًا باستخدام قوة حاسوبية أقل هو مجال بحث مستمر، خاصةً للأجهزة ذات الموارد المحدودة أو الاتصالات ذات السرعة الفائقة.

علاوة على ذلك، فإن معظم رموز تصحيح الأخطاء مصممة لتصحيح "الانعكاسات" - حيث يتحول 0 إلى 1 والعكس. الأخطاء التي تشمل إدخال أو حذف بتات، الشائعة في تدفقات البيانات غير المتزامنة، أكثر تعقيدًا في تصحيحها بكفاءة، وغالبًا ما تتطلب أنظمة تشفير مختلفة أو آليات متزامنة إضافية.

خدش على قرص أو تأثير أشعة كونية على إشارة بعيدة لم تعد عيوبًا قاتلة. بل هي لحظات قصيرة تُملَّس من خلال درع رياضي أنيق، يضمن بصمت سلامة جريان عالمنا الرقمي.

Eine leise Flüsternote der Daten, gesendet über Milliarden Kilometer vom Rand unseres Sonnensystems, erreicht die Erde mit jedem Bit unversehrt. Oder das vertraute Summen einer Compact Disc, die perfekt spielt, obwohl sichtbare Kratzer vorhanden sind. Beides verlässt sich auf eine unsichtbare Schicht sorgfältiger Redundanz.

Diese stille Wunderleistung, die Erkennung und Korrektur von Fehlern in übertragenen oder gespeicherten Informationen, bildet den Grundstein unseres digitalen Lebens. Dieses Gebiet entstand aus Frustration und mathematischem Einblick, begründet in der Erkenntnis, dass Rauschen und Unvollkommenheit in jedem Kommunikationskanal angelegt sind. Statt Fehler lediglich zu markieren und erneute Übertragung zu verlangen – was für Deep-Space-Proben unmöglich ist und für alltägliche Medien bestenfalls ein lästiges Problem darstellt – bauen fehlerkorrigierende Codes Resilienz direkt in die Botschaft ein.

Das grundlegende Konzept ist einfach: Füge sorgfältig strukturierte zusätzliche Informationen zu den ursprünglichen Daten hinzu. Diese Redundanz ermöglicht es dem Empfänger, nicht nur festzustellen, wo Verfälschungen aufgetreten sind, sondern oft auch, die ursprünglichen, unversehrten Daten wiederherzustellen, ohne erneut senden zu müssen. Der Preis ist Bandbreite, eine größere Anzahl von Bits, als strikt notwendig für die ursprüngliche Nachricht, doch die Auszahlung ist Zuverlässigkeit, selbst in den feindlichsten Umgebungen.

Hamming's Einblick und die Geburt der Parität Die Geschichte der modernen Fehlerkorrektur beginnt Ende der 1940er Jahre in den heiligen Hallen von [[Bell Labs]]. [[Richard Hamming]], ein Mathematiker, der an frühen Rechenmaschinen arbeitete, wurde zunehmend ärgerlich über die häufigen Abstürze, die von Einzelbitfehlern in Lochkartenlesern verursacht wurden. Diese Maschinen hielten an, leerten ihren Speicher und zwangen ihn dazu, seine Berechnungen neu zu starten, oft erst am Wochenende. Die Lösung seiner Kollegen bestand darin, ein einzelnes [[parity bit]] zu jedem Datenblock hinzuzufügen – ein zusätzliches Bit, das einfach anzeigte, ob die Anzahl der „1“ in dem Block gerade oder ungerade war. Dies ermöglichte die Fehlererkennung, aber nicht die Fehlerkorrektur. Wenn ein Fehler gefunden wurde, blieb das Gerät einfach stehen.

Hamming erkannte, dass, wenn man feststellen könnte, *welches* Bit fehlerhaft war, anstatt nur *dass* ein Fehler vorlag, Korrektur möglich würde. 1950 veröffentlichte er seine wegweisende Arbeit, in der er Hamming-Codes einführt, die erste Familie von fehlerkorrigierenden Codes, die in der Lage waren, Einzelbitfehler zu identifizieren und zu beheben. Sein Durchbruch bestand darin, Informationen so zu kodieren, dass die Position eines einzelnen Fehlers eindeutig aus einer Menge berechneter Paritätskontrollen bestimmt werden konnte. Es war ein grundlegender Schritt, der über die einfache Fehlererkennung hinausging und zur proaktiven Fehlerbehebung führte.

Der Arbeitstier: Reed-Solomon-Codes Während Hamming-Codes für bestimmte Anwendungen unverzichtbar erwiesen, wirft die reale Welt oft mehr als nur Einzelbitfehler. Burstfehler – bei denen mehrere aufeinanderfolgende Bits verfälscht werden – sind in physischen Medien wie Kratzen auf CDs oder störanfälligen Funkkanälen verbreitet. Für solche Szenarien wurden robusteren Codes benötigt. Hier kamen [[Reed-Solomon code]]s ins Spiel, ursprünglich 1960 von Irving Reed und Gustave Solomon entwickelt. Diese Blockcodes arbeiten mit Symbolen (Gruppen von Bits) statt einzelner Bits, wodurch sie besonders gut in der Lage sind, Burstfehler zu bewältigen.

Reed-Solomon-Codes erreichen dies, indem sie Daten als Polynome über endlichen Körpern behandeln. Der Encoder berechnet dieses Polynom an mehreren Punkten, und diese berechneten Punkte, zusammen mit den ursprünglichen Daten, werden übertragen. Der Empfänger kann dann das ursprüngliche Polynom rekonstruieren, selbst wenn einige Punkte verloren gegangen oder verfälscht wurden, ähnlich wie die Bestimmung einer Kurve anhand einiger bekannter Punkte. Diese mathematische Eleganz machte sie allgegenwärtig. Sie bilden die Grundlage digitaler Audio (CDs), Video (DVDs, Blu-ray), QR-Codes und sind für Deep-Space-Kommunikation entscheidend, wo Signale schwach und Störungen konstant sind.

Auf der Suche nach dem Shannon-Limit Das theoretische Limit einer zuverlässigen Kommunikation über einen störanfälligen Kanal wurde 1948 von [[Claude Shannon]] mit seinem störanfälligen-Kanal-Codierungstheorem etabliert. Shannons Arbeit enthüllte, dass es eine maximale Rate gibt, mit der Informationen übertragen werden können, bei der die Fehlerwahrscheinlichkeit beliebig klein bleibt, selbst in Gegenwart von Rauschen. Für Jahrzehnte arbeiteten Ingenieure und Mathematiker daran, Codes zu entwickeln, die diesem theoretischen [[Shannon limit]] annähern konnten.

Moderne fehlerkorrigierende Codes, wie Turbo-Codes (eingeführt in den frühen 1990er Jahren) und LDPC codes (ursprünglich von Robert Gallager 1960 vorgeschlagen, aber aufgrund der Rechenkomplexität bis Ende der 1990er Jahre weitgehend ignoriert), machten bemerkenswerte Fortschritte. Diese Codes verwenden iterative Decodieralgorithmen, die Informationen zwischen mehreren einfachen Decodern austauschen und so schrittweise die Wahrscheinlichkeit einer korrekten Decodierung erhöhen. Insbesondere LDPC-Codes sind heute zentral für Hochgeschwindigkeitskommunikationsstandards wie DVB-S2 (digitales Fernsehen), WiMAX und 10GBase-T Ethernet, wodurch Grenzen in störanfälligen Umgebungen neu definiert werden.

Was wir immer noch nicht wissen

Obwohl Codes für bestimmte Kanalmodelle das Shannon-Limit annähern können, sind reale Kanäle selten perfekt verstanden oder statisch. Die dynamische Anpassung der Fehlerkorrektur an sich verändernde Rauschbedingungen bleibt eine komplexe Herausforderung.

Die Rechenlast für das Decodieren dieser fortgeschrittenen Codes, obwohl erheblich reduziert, ist immer noch beträchtlich. Die Suche nach Wegen, nahezu optimale Leistung mit weniger Rechenleistung zu erzielen, ist ein aktives Forschungsfeld, insbesondere für geräte mit begrenzten Ressourcen oder für ultraschnelle Kommunikation.

Außerdem sind die meisten fehlerkorrigierenden Codes darauf ausgelegt, „Bitflips“ zu behandeln – also Fälle, in denen eine 0 zu einer 1 oder umgekehrt wird. Fehler, bei denen Bits eingefügt oder gelöscht werden, wie sie in asynchronen Datenströmen häufig vorkommen, sind weitaus schwieriger zu korrigieren und erfordern oft andere Kodierungsschemata oder zusätzliche Synchronisationsmechanismen.

Ein Kratzer auf einer Scheibe oder der Einfluss kosmischer Strahlung auf ein entferntes Signal sind nicht länger tödliche Mängel. Stattdessen sind sie nur kurze Störungen, die von einer eleganten mathematischen Schutzschicht ausgebügelt werden, die stumm bleibt und die Integrität unseres digitalen Universums gewährleistet.

우리 태양계 가장자리에서 수십억 킬로미터나 떨어진 곳에서 보낸 미약한 데이터 속삭임이, 모든 비트이 손상되지 않은 채 지구에 도달한다. 또는, 긁힌 자국이 보이는 컴팩트 디스크가 완벽하게 재생되는 익숙한 썸 소리도 마찬가지다. 이 둘 모두 눈에 보이지 않는 세심한 중복성을 기반으로 한다.

오늘날 디지털 세계의 기반이 되는 이 조용한 기적은, 전송되거나 저장된 정보에 포함된 오류를 탐지하고 수정하는 능력입니다. 이 분야는 좌절과 수학적 통찰에서 비롯되었습니다. 모든 통신 채널에는 소음과 불완전성이 고유하게 내재되어 있다는 인식이 뿌리가 되었습니다. 오류를 단순히 표시하고 재전송을 요구하는 것보다—심우주 탐사선에는 불가능한 일이고 일상적인 미디어에서는 단순한 불편에 불과한 일—오류 수정 코드는 메시지 자체에 내재적인 회복력을 구축합니다.

기본적인 개념은 간단합니다. 원래 데이터에 신중하게 구성된 추가 정보를 더하는 것입니다. 이러한 중복성 덕분에 수신자는 오염이 어디에서 발생했는지를 특정할 뿐 아니라, 재전송을 요구하지 않고도 원래의 완전한 데이터를 다시 구축할 수 있습니다. 비용은 대역폭입니다. 원래 메시지에 필요한 것보다 더 많은 비트가 전송되지만, 그 대가로 가장 혹독한 환경에서도 신뢰성을 확보할 수 있습니다.

햄밍의 통찰과 패리티의 탄생 현대 오류 수정의 이야기는 1940년대 말, [[Bell Labs]]의 성스러운 연구실에서 시작됩니다. [[Richard Hamming]]이라는 수학자는 초기 컴퓨터 기계와 함께 일하면서 펀치 카드 리더에서 발생하는 단일 비트 오류로 인한 빈번한 충돌에 점점 짜증을 내기 시작했습니다. 이러한 기계는 멈추고 메모리를 던져버리며, 종종 주말 동안 그의 계산을 다시 시작하게 했습니다. 동료들의 해결책은 각 데이터 블록에 단일 [[parity bit]]을 추가하는 것이었습니다. 이는 단순히 블록 내 '1'의 개수가 짝수인지 홀수인지를 나타내는 추가 비트였습니다. 이는 오류를 탐지하는 데는 유용했지만, 수정은 불가능했습니다. 오류가 발견되면 기계는 단순히 멈췄습니다.

햄밍은 오류가 존재한다는 것을 알기만 한다면 아니라, *어떤* 비트에 오류가 있는지를 특정할 수 있다면 수정이 가능하다는 것을 깨달았습니다. 1950년, 그는 단일 비트 오류를 식별하고 수정할 수 있는 최초의 오류 수정 코드인 햄밍 코드를 도입한 학문적 기념물을 발표했습니다. 그의 돌파구는 정보를 인코딩하여 단일 오류의 위치를 계산된 패리티 검사 집합으로부터 유일하게 결정할 수 있도록 만드는 것이었습니다. 이는 단순한 오류 탐지에서 능동적인 오류 수리로의 중요한 발전이었습니다.

핵심 기술: 리드-솔로몬 코드 햄밍 코드는 특정한 응용 분야에서 매우 유용했지만, 현실 세계는 단일 비트 오류만 던져주는 법이 아닙니다. 버스트 오류—여러 개의 연속된 비트가 손상되는 오류—는 긁힌 CD나 잡음이 많은 라디오 채널과 같은 물리적 매체에서 흔합니다. 이러한 시나리오에서는 더 견고한 코드가 필요했습니다. 이에 [[Reed-Solomon code]]s가 등장했습니다. 이 코드는 1960년에 이븐 리드와 구스타브 솔로몬이 처음 제안한 블록 코드로, 개별 비트가 아니라 비트 그룹인 '심볼'을 다루는 것이 특징입니다. 이는 버스트 오류를 처리하는 데 특히 효과적입니다.

리드-솔로몬 코드는 데이터를 유한체 상의 다항식으로 처리하여 이를 달성합니다. 인코더는 이 다항식을 여러 지점에서 평가하고, 이 평가 지점과 원래 데이터를 함께 전송합니다. 수신자는 일부 지점이 손실되거나 손상된 경우에도 원래 다항식을 재구성할 수 있습니다. 이는 몇 개의 알려진 지점으로 곡선을 결정하는 것과 비슷합니다. 이러한 수학적 우아함은 이 코드를 디지털 오디오(CD), 비디오(DVD, 블루레이), QR 코드의 핵심 기술로 만들었으며, 신호가 약하고 간섭이 끊임없는 심우주 통신에서도 필수적입니다.

쇼넌 한계에 도전하다 노이즈가 있는 채널에서 신뢰성 있는 통신의 이론적 한계는 1948년 [[Claude Shannon]]의 노이즈 채널 코딩 정리로 확립되었습니다. 쇼넌의 연구는 노이즈가 존재하더라도 정보를 임의로 작은 오류 확률로 전송할 수 있는 최대 속도가 있다는 것을 밝혀냈습니다. 수십 년 동안 엔지니어와 수학자들은 이 이론적 [[Shannon limit]]에 가까워질 수 있는 코드를 개발하기 위해 노력했습니다.

현대 오류 수정 코드로는 터보 코드(1990년대 초에 도입됨)와 LDPC codes(1960년에 Robert Gallager가 처음 제안했지만 계산 복잡도로 인해 1990년대 말까지 거의 무시되었음)가 있습니다. 이러한 코드는 여러 간단한 디코더 간에 정보를 교환하는 반복 디코딩 알고리즘을 사용하여, 올바른 디코딩의 확률을 점차 향상시킵니다. 특히 LDPC 코드는 DVB-S2(디지털 방송), WiMAX, 10GBase-T 이더넷과 같은 고속 통신 표준의 핵심 요소로 자리 잡아, 잡음이 많은 환경에서의 가능성을 확장하고 있습니다.

여전히 알지 못하는 것들

특정 채널 모델에 대해서는 코드가 쇼넌 한계에 근접할 수 있지만, 실제 세계의 채널은 거의 완벽하게 이해되거나 정적이지 않습니다. 변화하는 노이즈 조건에 따라 오류 수정을 동적으로 조정하는 것은 여전히 복잡한 과제입니다.

이러한 고급 코드의 디코딩 계산 부하는 크게 줄어들었지만 여전히 상당합니다. 제한된 자원을 가진 장치나 초고속 통신에서 근접 최적 성능을 달성하기 위한 방법을 찾는 것은 지속적인 연구 주제입니다.

또한 대부분의 오류 수정 코드는 '비트 뒤집기'—0이 1이 되거나 그 반대인 경우—를 처리하도록 설계되었습니다. 비동기 데이터 스트림에서 흔한 비트 삽입 또는 삭제 오류는 효율적으로 수정하는 것이 훨씬 더 어렵습니다. 이는 보통 다른 인코딩 방식이나 추가 동기화 메커니즘을 필요로 합니다.

디스크의 긁힘이나 먼 곳에서의 우주선 신호에 영향을 주는 우주 방사선은 더 이상 치명적인 결함이 아닙니다. 이들은 수학적 방패의 일시적인 틈으로 매끄럽게 지나가며, 우리의 디지털 우주의 무결성을 침묵 속에서 지켜줍니다.

Слабый шепот данных, посланный через миллиарды километров с края нашей солнечной системы, достигает Земли с каждым битом целым. Или привычное жужжание компакт-диска, играющего безупречно, несмотря на видимые царапины. Оба зависят от невидимого слоя тщательной избыточности.

Эта тихая чудесная вещь — обнаружение и исправление ошибок в передаваемой или хранимой информации — лежит в основе большей части нашего цифрового мира. Это направление возникло из разочарования и математического прозрения, основанного на понимании того, что шум и несовершенство встроены в каждый канал связи. Вместо простого обнаружения ошибок и требования повторной передачи — невозможной задачи для космических зондов или тривиального неудобства для повседневных средств массовой информации — коды исправления ошибок напрямую вносят устойчивость в само сообщение.

Основная идея проста: добавляйте тщательно структурированную дополнительную информацию к исходным данным. Эта избыточность позволяет получателю не только определить, где произошло повреждение, но часто и восстановить оригинальные, неповреждённые данные, не требуя повторной передачи. Стоимость — это пропускная способность, больший объём битов, отправляемых, чем строго необходимо для исходного сообщения, но выгода — надёжность, даже в самых враждебных условиях.

Прозрение Хэмминга и рождение чётности История современной коррекции ошибок начинается в конце 1940-х годов, в святилищах [[Bell Labs]]. [[Richard Hamming]], математик, работавший с ранними вычислительными машинами, всё чаще раздражался из-за частых сбоев, вызванных ошибками в одном бите в читателях перфокарт. Эти машины останавливались, выгружали память, и заставляли его перезапускать вычисления, часто на выходных. Решение его коллег заключалось в добавлении одного [[parity bit]] к каждому блоку данных — дополнительного бита, который просто указывал, чётное ли количество '1' в блоке. Это позволяло обнаруживать ошибки, но не исправлять их. Если ошибка находилась, машина просто останавливалась.

Хэмминг осознал, что если можно определить, *какой* бит содержит ошибку, а не просто *то, что* ошибка существует, то исправление становится возможным. В 1950 году он опубликовал свою основополагающую работу, в которой представил коды Хэмминга — первую группу кодов исправления ошибок, способных идентифицировать и исправлять ошибки в одном бите. Его прорыв заключался в том, что он кодировал информацию так, чтобы позицию любой одной ошибки можно было однозначно определить из набора рассчитанных проверок чётности. Это стало фундаментальным шагом, переходом от простого обнаружения ошибок к активному их устранению.

Рабочая лошадка: Коды Рида-Соломона Хотя коды Хэмминга оказались чрезвычайно полезны для определённых приложений, реальный мир часто сталкивает с ошибками, превышающими просто ошибки в одном бите. Пакетные ошибки — когда несколько последовательных битов повреждены — распространены в физических носителях, таких как царапины на компакт-дисках или шумные радиоканалы. Для этих сценариев требовались более надёжные коды. На сцену выходят [[Reed-Solomon code]]s, впервые задуманные в 1960 году Ирвингом Ридом и Густавом Соломоном. Эти блочные коды работают с символами (группами битов), а не с отдельными битами, что делает их исключительно хорошими для обработки пакетных ошибок.

Коды Рида-Соломона достигают этого, рассматривая данные как полиномы над конечными полями. Кодировщик оценивает этот полином в нескольких точках, и эти оцененные точки, вместе с оригинальными данными, передаются. Получатель может затем восстановить исходный полином, даже если некоторые точки утеряны или повреждены, подобно определению кривой из нескольких известных точек. Эта математическая элегантность сделала их повсеместными. Они являются основой цифрового аудио (CD), видео (DVD, Blu-ray), QR-кодов и критически важны для связи в глубоком космосе, где сигналы слабы, а помехи постоянны.

Поиски предела Шеннона Теоретический предел надёжной связи по шумному каналу был установлен [[Claude Shannon]] в 1948 году с его теоремой о кодировании шумного канала. Работа Шеннона показала, что существует максимальная скорость, с которой информацию можно передавать с произвольно малой вероятностью ошибки, даже при наличии шума. В течение десятилетий инженеры и математики трудились над разработкой кодов, которые могли бы приблизиться к этому теоретическому [[Shannon limit]].

Современные коды исправления ошибок, такие как Турбокоды (введённые в начале 1990-х годов) и LDPC codes (изначально предложенные Robert Gallager в 1960 году, но в основном проигнорированные до конца 1990-х годов из-за вычислительной сложности), достигли впечатляющего прогресса. Эти коды используют итеративные алгоритмы декодирования, которые обмениваются информацией между несколькими более простыми декодерами, постепенно повышая вероятность правильного декодирования. В частности, коды LDPC сейчас находятся в центре высокоскоростных стандартов связи, таких как DVB-S2 (цифровое телевидение), WiMAX и 10GBase-T Ethernet, расширяя границы возможного в шумных условиях.

То, что мы всё ещё не знаем

Хотя коды могут приближаться к пределу Шеннона для определённых моделей каналов, реальные каналы редко полностью понятны или статичны. Адаптация коррекции ошибок к изменяющимся условиям шума остаётся сложной задачей.

Вычислительные издержки для декодирования этих передовых кодов, хотя и значительно снизились, всё ещё значительны. Поиск путей достижения почти оптимальной производительности с меньшей вычислительной мощностью остаётся актуальной областью исследований, особенно для устройств с ограниченными ресурсами или сверхвысокоскоростной связи.

Кроме того, большинство кодов исправления ошибок разработано для обработки «переворотов битов» — когда 0 становится 1 или наоборот. Ошибки, связанные с вставкой или удалением битов, распространённые в асинхронных потоках данных, гораздо сложнее корректировать эффективно, часто требуя различных схем кодирования или дополнительных механизмов синхронизации.

Царапина на диске или воздействие космического излучения на удалённый сигнал больше не являются фатальными дефектами. Вместо этого они становятся кратковременными помехами, сглаженными элегантным математическим щитом, тихо обеспечивающим целостность нашего цифрового мира.

डेटा की एक झलक, जो हमारे सौर मंडल के किनारे से अरबों किलोमीटर की दूरी तय करके भेजी जाती है, प्रत्येक बिट के साथ पृथ्वी तक पहुँच जाती है। या फिर एक कॉम्पैक्ट डिस्क की परिचित ध्वनि, जो दिखाई देने वाली खरोंचों के बावजूद बिल्कुल सही तरीके से चलती है। दोनों में एक अदृश्य परत के ध्यान से बनाए गए अतिरिक्त तत्व पर निर्भरता होती है।

इस शांत चमत्कार, जो संचारित या संगृहीत जानकारी में त्रुटियों का पता लगाने और सुधारने के काम को धारण करता है, हमारी डिजिटल दुनिया का आधार है। यह क्षेत्र असंतोष और गणितीय दृष्टिकोण का जन्मदाता है, जो समझ के साथ जड़ रखता है कि शोर और अपूर्णता प्रत्येक संचार चैनल में अभिन्न है। त्रुटियों को केवल चिह्नित करके और पुनः-संचार की मांग करके नहीं, जो अंतरिक्ष अन्वेषण के लिए असंभव है या दिनचर्या मीडिया के लिए एक छोटी असुविधा है, बल्कि संदेश में सीधे प्रतिरोधकता बनाने वाले त्रुटि-सुधार कोड तकनीकी स्वयं में शामिल करते हैं।

मूल अवधारणा सरल है: मूल डेटा में ध्यानपूर्वक संरचित अतिरिक्त जानकारी जोड़ें। इस पुनरावृत्ति के कारण प्राप्तकर्ता केवल दोष के स्थान का पता लगा सकता है, बल्कि अक्सर पुनः प्राप्त करने की आवश्यकता के बिना मूल, अछूते डेटा को पुनर्निर्माण कर सकता है। लागत बैंडविड्थ है, जो मूल संदेश के लिए आवश्यकता से अधिक बिटों की मात्रा भेजती है, लेकिन लाभ विश्वसनीयता है, यहां तक कि सबसे खतरनाक वातावरण में भी।

हैमिंग की दृष्टि और पारिता का जन्म आधुनिक त्रुटि सुधार की कहानी 1940 के अंत में शुरू होती है, [[Bell Labs]] के पवित्र हॉल में। [[Richard Hamming]], एक गणितज्ञ, जो प्रारंभिक कंप्यूटिंग मशीनों के साथ काम कर रहा था, पंच कार्ड रीडर में एकल-बिट त्रुटियों के कारण लगातार क्रैश होने से बढ़ते रोष में आ गया था। ये मशीनें रूक जाती थीं, अपनी मेमोरी को खाली कर देती थीं और उसे अक्सर शनिवार-रविवार के दौरान अपनी गणनाओं को पुनः शुरू करने को मजबूर कर देती थीं। उसके सहयोगियों का समाधान हर डेटा ब्लॉक में एकल [[parity bit]] जोड़ना था - एक अतिरिक्त बिट जो ब्लॉक में '1' की संख्या सम या विषम होने का संकेत देता था। इससे त्रुटि का पता लगाना संभव हो गया, लेकिन सुधार नहीं। यदि कोई त्रुटि पाई गई, तो मशीन सिर्फ रूक जाती थी।

हैमिंग ने यह समझ गया कि यदि एक व्यक्ति निर्धारित कर सके कि कौन-सा बिट त्रुटिपूर्ण है, बस इतना नहीं कि त्रुटि के अस्तित्व का पता है, तो सुधार संभव हो जाएगा। 1950 में, उसने अपने अभिनव कार्य को प्रकाशित किया, जिसमें हैमिंग कोड का परिचय दिया गया, पहला कोड परिवार जो एकल-बिट त्रुटियों की पहचान और सुधार करने में सक्षम है। उसकी उपलब्धि यह थी कि जानकारी को इस प्रकार एन्कोड किया गया कि किसी भी एकल त्रुटि की स्थिति को एक सेट से पारिता जाँचों के आधार पर अद्वितीय रूप से निर्धारित किया जा सकता है। यह एक मूलभूत कदम था, जो सरल त्रुटि पहचान से आगे बढ़कर सक्रिय त्रुटि सुधार की ओर बढ़ गया।

मुख्य बल: रीड-सोलोमन कोड हालांकि हैमिंग कोड ने कुछ अनुप्रयोगों के लिए महत्वपूर्ण साबित हुए, वास्तविक दुनिया अक्सर केवल एकल-बिट त्रुटियों से अधिक नहीं उत्पन्न करती है। बर्स्ट त्रुटियां - जहां कई क्रमिक बिट्स दोषपूर्ण हो जाते हैं - खरोंचे हुए सीडी या शोर वाले रेडियो चैनल जैसे भौतिक मीडिया में सामान्य हैं। इन परिदृश्यों के लिए अधिक टिकाऊ कोड की आवश्यकता होती है। यहां [[Reed-Solomon code]] के कोड आते हैं, जिनकी अवधारणा 1960 में इरविंग रीड और गस्ताव सोलोमन द्वारा प्रस्तावित की गई थी। ये ब्लॉक कोड व्यक्तिगत बिट्स के बजाय संकेतों (बिट्स के समूह) पर कार्य करते हैं, जिससे बर्स्ट त्रुटियों के साथ निपटने में वे विशेष रूप से अच्छे होते हैं।

रीड-सोलोमन कोड इसे अंतरित समान फील्ड पर डेटा को बहुपद के रूप में देखकर प्राप्त करते हैं। एन्कोडर इस बहुपद के कई बिंदुओं पर मूल्यांकन करता है, और इन मूल्यांकित बिंदुओं के साथ मूल डेटा को भेजा जाता है। प्राप्तकर्ता फिर इन बिंदुओं के कुछ ज्ञात बिंदुओं के समान एक वक्र का निर्धारण करके मूल बहुपद को पुनर्निर्माण कर सकता है। इस गणितीय सुंदरता ने उन्हें व्यापक बना दिया। वे डिजिटल ऑडियो (सीडी), वीडियो (डीवीडी, ब्लू-रे), क्यूआर कोड के आधार हैं, और दूरस्थ अंतरिक्ष संचार के लिए आवश्यक हैं, जहां संकेत कमजोर होते हैं और अवरोधन निरंतर रहता है।

शैनन सीमा तक पहुंचना एक शोर वाले चैनल पर विश्वसनीय संचार की सैद्धांतिक सीमा को 1948 में [[Claude Shannon]] द्वारा अपने शोर-चैनल कोडिंग प्रमेय के साथ स्थापित किया गया था। शैनन के कार्य ने खुलासा किया कि शोर की उपस्थिति में भी एक अधिकतम दर है जिस पर जानकारी को अत्यधिक छोटी त्रुटि संभावना के साथ भेजा जा सकता है। दशकों तक इंजीनियरों और गणितज्ञों ने इस सैद्धांतिक [[Shannon limit]] के करीब पहुंचने वाले कोड विकसित करने के लिए काम किया।

आधुनिक त्रुटि-सुधार कोड, जैसे टर्बो कोड (1990 के शुरुआत में पेश किए गए) और LDPC code (1960 में Robert Gallager द्वारा प्रस्तावित किए गए लेकिन 1990 के अंत तक कंप्यूटेशनल जटिलता के कारण लगभग अनदेखे रहे), उल्लेखनीय प्रगति कर चुके हैं। इन कोडों में अनुक्रमिक डिकोडिंग एल्गोरिदम का उपयोग किया जाता है, जो कई सरल डिकोडर्स के बीच जानकारी का आदान-प्रदान करते हैं, जिससे सही डिकोडिंग की संभावना धीरे-धीरे सुधारती है। विशेष रूप से, एलडीपीसी कोड अब डीवीबी-एस2 (डिजिटल टेलीविजन), वाईमैक्स और 10जीबेस-टी ईथरनेट जैसे उच्च गति के संचार मानकों के केंद्र में हैं, जो शोर वाले वातावरण में संभव के सीमा तक पहुंचने की सीमा को बढ़ा रहे हैं।

जो हम अभी नहीं जानते

हालांकि कुछ चैनल मॉडल के लिए कोड शैनन सीमा के करीब पहुंच सकते हैं, वास्तविक दुनिया के चैनल अक्सर पूरी तरह से समझे या स्थिर नहीं होते हैं। परिवर्तित शोर की स्थितियों में त्रुटि सुधार को गतिशील रूप से अनुकूलित करना अभी भी एक जटिल चुनौती है।

इन उन्नत कोडों के डिकोडिंग के लिए गणना अतिरिक्त भार, हालांकि बहुत कम कम हो गया है, अभी भी बड़ा है। कम गणना शक्ति के साथ लगभग अनुकूलतम प्रदरसन प्राप्त करने के तरीके खोजना अभी भी शोध का एक जारी रहने वाला क्षेत्र है, विशेष रूप से संसाधन-सीमित उपकरणों या अत्यधिक गति वाले संचार के लिए।

इसके अलावा, अधिकांश त्रुटि-सुधार कोड 'बिट फ्लिप्स' - जहां 0 1 हो जाता है या इसके विपरीत - के संसाधन के लिए डिज़ाइन किए गए हैं। असिंक्रोनस डेटा स्ट्रीम में बिट्स के एक्सपोज़र या हटाने के त्रुटियां अधिक कुशल रूप से सुधारने में अधिक कठिन हैं, जो अक्सर अलग-अलग कोडिंग योजनाओं या अतिरिक्त सिंक्रोनाइज़ेशन तंत्रों की आवश्यकता करती हैं।

एक डिस्क पर खरोंच या दूर के संकेत पर एक अंतरिक्ष किरण का प्रभाव अब घातक दोष नहीं है। बल्कि, ये एकल अंतराल एक सुंदर गणितीय ढाल द्वारा शांत कर दिए जाते हैं, जो शांत रूप से हमारी डिजिटल ब्रह्मांड की अखंडता की गारंटी देते हैं।

Error-Correcting Codes