В теории информации и теории кодирования с приложениями в информатике и телекоммуникациях обнаружение и исправление ошибок ( EDAC ) или контроль ошибок представляют собой методы, которые обеспечивают надежную доставку цифровых данных по ненадежным каналам связи . Многие каналы связи подвержены канальному шуму , поэтому во время передачи от источника к приемнику могут возникать ошибки. Методы обнаружения ошибок позволяют обнаружить такие ошибки, а коррекция ошибок во многих случаях позволяет восстановить исходные данные.
Обнаружение ошибок — это обнаружение ошибок, вызванных шумом или другими помехами во время передачи от передатчика к приемнику.
Исправление ошибок — это обнаружение ошибок и восстановление исходных безошибочных данных.
В классической древности переписчикам еврейской Библии платили за работу в зависимости от количества стихов (стихов). Поскольку прозаические книги Библии почти никогда не писались стихами, переписчикам, чтобы оценить объем работы, приходилось считать буквы. [1] Это также помогло обеспечить точность передачи текста при изготовлении последующих копий. [2] [3] Между 7 и 10 веками нашей эры группа еврейских писцов формализовала и расширила это, чтобы создать Цифровую Масору , чтобы гарантировать точное воспроизведение священного текста. Он включал подсчет количества слов в строке, разделе, книге и группах книг, учет среднего стежка книги, статистику использования слов и комментарии. [1] Стандарты стали такими, что отклонение даже в одной букве свитка Торы считалось недопустимым. [4] Эффективность их метода исправления ошибок была подтверждена точностью копирования на протяжении веков, продемонстрированной открытием в 1947–1956 годах свитков Мертвого моря , датируемых ок. 150 г. до н.э.-75 г. н.э. [5]
Современная разработка кодов исправления ошибок приписывается Ричарду Хэммингу в 1947 году. [6] Описание кода Хэмминга появилось в книге Клода Шеннона «Математическая теория связи» [7] и было быстро обобщено Марселем Дж. Голеем . [8]
Все схемы обнаружения и исправления ошибок добавляют к сообщению некоторую избыточность (т. е. некоторые дополнительные данные), которую получатели могут использовать для проверки согласованности доставленного сообщения и для восстановления данных, которые были признаны поврежденными. Схемы обнаружения и исправления ошибок могут быть как систематическими , так и несистематическими. В систематической схеме передатчик отправляет исходные (безошибочные) данные и присоединяет фиксированное количество проверочных битов (или данных четности ), которые извлекаются из битов данных с помощью некоторого алгоритма кодирования. Если требуется обнаружение ошибок, получатель может просто применить тот же алгоритм к полученным битам данных и сравнить его выходные данные с полученными проверочными битами; если значения не совпадают, в какой-то момент передачи произошла ошибка. Если требуется исправление ошибок, приемник может применить алгоритм декодирования к полученным битам данных и полученным контрольным битам, чтобы восстановить исходные данные без ошибок. В системе, использующей несистематический код, исходное сообщение преобразуется в закодированное сообщение, несущее ту же информацию и имеющее по крайней мере столько же битов, сколько и исходное сообщение.
Хорошая эффективность контроля ошибок требует, чтобы схема была выбрана на основе характеристик канала связи. К моделям с общим каналом относятся модели без памяти , в которых ошибки возникают случайным образом и с определенной вероятностью, и динамические модели, в которых ошибки возникают преимущественно пакетно . Следовательно, коды обнаружения и исправления ошибок обычно можно разделить на коды обнаружения/исправления случайных ошибок и коды обнаружения/исправления пакетных ошибок . Некоторые коды также могут быть пригодны для сочетания случайных ошибок и пакетов ошибок.
Если характеристики канала не могут быть определены или сильно варьируются, схему обнаружения ошибок можно объединить с системой повторной передачи ошибочных данных. Это известно как автоматический запрос повторения (ARQ) и чаще всего используется в Интернете. Альтернативным подходом к контролю ошибок является гибридный автоматический запрос повторения (HARQ), который представляет собой комбинацию ARQ и кодирования с коррекцией ошибок.
Существует три основных типа исправления ошибок: [9]
Автоматический запрос повторения (ARQ) — это метод контроля ошибок при передаче данных, в котором для обеспечения надежной передачи данных используются коды обнаружения ошибок, сообщения подтверждения и/или отрицательного подтверждения, а также тайм-ауты . Подтверждение — это сообщение, отправленное получателем, чтобы указать, что он правильно получил кадр данных .
Обычно, когда передатчик не получает подтверждение до истечения тайм-аута (т. е. в течение разумного периода времени после отправки кадра данных), он повторно передает кадр до тех пор, пока он либо не будет правильно принят, либо пока ошибка не сохранится после заранее определенного количества повторных передач. .
Три типа протоколов ARQ: ARQ с остановкой и ожиданием , ARQ с возвратом-N и ARQ с выборочным повторением .
ARQ подходит, если канал связи имеет переменную или неизвестную пропускную способность , как в случае с Интернетом. Однако ARQ требует наличия обратного канала , что приводит к возможному увеличению задержки из-за повторных передач и требует обслуживания буферов и таймеров для повторных передач, что в случае перегрузки сети может создать нагрузку на сервер и общую пропускную способность сети. [10]
Например, ARQ используется в коротковолновых радиоканалах передачи данных в форме ARQ-E или в сочетании с мультиплексированием как ARQ-M .
Прямое исправление ошибок (FEC) — это процесс добавления избыточных данных , таких как код исправления ошибок (ECC), к сообщению, чтобы оно могло быть восстановлено получателем, даже если некоторое количество ошибок (в зависимости от возможностей кода) используемые) вводятся либо в процессе передачи, либо при хранении. Поскольку получателю не нужно запрашивать отправителя о повторной передаче данных, обратный канал не требуется для прямого исправления ошибок. Коды, исправляющие ошибки, используются в связи нижнего уровня , таких как сотовая сеть , высокоскоростная оптоволоконная связь и Wi-Fi , [11] [12] , а также для надежного хранения на таких носителях, как флэш-память , жесткий диск и БАРАН . [13]
Коды, исправляющие ошибки, обычно различают сверточные коды и блочные коды :
Теорема Шеннона является важной теоремой в прямом исправлении ошибок и описывает максимальную скорость передачи данных , при которой возможна надежная связь по каналу, который имеет определенную вероятность ошибки или отношение сигнал/шум (SNR). Этот строгий верхний предел выражается в пропускной способности канала . Более конкретно, теорема гласит, что существуют коды, в которых с увеличением длины кодирования вероятность ошибки на дискретном канале без памяти может быть сделана сколь угодно малой при условии, что скорость кода меньше пропускной способности канала. Скорость кода определяется как доля k/n из k исходных символов и n закодированных символов.
Фактическая максимальная допустимая скорость кода зависит от используемого кода исправления ошибок и может быть ниже. Это связано с тем, что доказательство Шеннона носило только экзистенциальный характер и не показывало, как создавать оптимальные коды, имеющие эффективные алгоритмы кодирования и декодирования.
Гибридный ARQ представляет собой комбинацию ARQ и прямого исправления ошибок. Существует два основных подхода: [10]
Последний подход особенно привлекателен на канале стирания при использовании кода стирания без скорости .
Обнаружение ошибок чаще всего реализуется с использованием подходящей хеш-функции (или, в частности, контрольной суммы , проверки циклическим избыточным кодом или другого алгоритма). Хэш-функция добавляет к сообщению тег фиксированной длины , что позволяет получателям проверять доставленное сообщение путем повторного вычисления тега и сравнения его с предоставленным.
Существует огромное разнообразие различных конструкций хеш-функций. Однако некоторые из них получили особенно широкое применение либо из-за их простоты, либо из-за их пригодности для обнаружения определенных типов ошибок (например, производительность проверки циклическим избыточным кодом при обнаружении пакетных ошибок ).
Код, исправляющий случайные ошибки, основанный на кодировании на минимальном расстоянии , может обеспечить строгую гарантию количества обнаруживаемых ошибок, но он может не защитить от атаки прообраза .
Код повторения — это схема кодирования, которая повторяет биты по каналу для обеспечения безошибочной связи. Учитывая поток передаваемых данных, данные делятся на блоки битов. Каждый блок передается некоторое заранее определенное количество раз. Например, чтобы отправить битовую комбинацию 1011 , четырехбитный блок можно повторить три раза, создавая таким образом 1011 1011 1011 . Если этот двенадцатибитный шаблон был получен как 1010 1011 1011 – где первый блок отличается от двух других – произошла ошибка.
Код повторения очень неэффективен и может вызывать проблемы, если ошибка возникает точно в одном и том же месте для каждой группы (например, 1010, 1010, 1010 в предыдущем примере будет считаться правильным). Преимущество кодов повторения состоит в том, что они чрезвычайно просты и фактически используются при некоторых передачах номеров станций . [14] [15]
Бит четности — это бит, который добавляется к группе исходных битов, чтобы гарантировать, что количество установленных битов (т. е. бит со значением 1) в результате будет четным или нечетным. Это очень простая схема, которую можно использовать для обнаружения одной или любого другого нечетного числа (т. е. трех, пяти и т. д.) ошибок в выходных данных. Если четное количество перевернутых битов приведет к тому, что бит четности будет выглядеть правильным, даже если данные ошибочны.
Биты четности, добавляемые к каждому отправленному слову , называются проверками поперечного избыточного кода , а те, которые добавляются в конце потока слов , называются проверками продольного избыточного кода . Например, если в каждое из m-битных слов добавлен бит четности, показывающий, было ли в этом слове нечетное или четное количество единиц, будет обнаружено любое слово с единственной ошибкой. Однако неизвестно, где именно в слове ошибка. Если, кроме того, после каждого потока из n слов отправляется сумма четности, каждый бит которой показывает, было ли нечетное или четное количество единиц в этой битовой позиции, отправленной в самой последней группе, то точное положение ошибки можно определить и исправить ошибку. Однако этот метод гарантированно эффективен только в том случае, если в каждой группе из n слов имеется не более 1 ошибки. Чем больше битов исправления ошибок, тем больше ошибок можно обнаружить и в некоторых случаях исправить.
Существуют и другие методы группировки битов.
Контрольная сумма сообщения представляет собой модульную арифметическую сумму кодовых слов сообщения фиксированной длины (например, байтовых значений). Сумма может быть инвертирована посредством операции дополнения до единицы перед передачей для обнаружения непреднамеренных сообщений с нулевыми значениями.
Схемы контрольной суммы включают биты четности, контрольные цифры и проверки продольного избыточного кода . Некоторые схемы контрольных сумм, такие как алгоритм Дамма , алгоритм Луна и алгоритм Верхуффа , специально разработаны для обнаружения ошибок, обычно вносимых людьми при записи или запоминании идентификационных номеров.
Проверка циклическим избыточным кодом (CRC) — это незащищенная хеш-функция , предназначенная для обнаружения случайных изменений цифровых данных в компьютерных сетях. Он не подходит для обнаружения злонамеренно внесенных ошибок. Он характеризуется указанием порождающего полинома , который используется в качестве делителя при делении полинома в длину над конечным полем , принимая входные данные в качестве делимого . Остаток становится результатом .
CRC обладает свойствами, которые делают его хорошо подходящим для обнаружения пакетов ошибок . CRC особенно легко реализовать на аппаратном уровне, и поэтому они широко используются в компьютерных сетях и устройствах хранения данных, таких как жесткие диски .
Бит четности можно рассматривать как 1-битный CRC особого случая.
Вывод криптографической хеш-функции , также известный как дайджест сообщения , может обеспечить надежную гарантию целостности данных , независимо от того, являются ли изменения данных случайными (например, из-за ошибок передачи) или внесены злонамеренно. Любое изменение данных, скорее всего, будет обнаружено по несовпадающему значению хеш-функции. Более того, при наличии некоторого хеш-значения обычно невозможно найти некоторые входные данные (кроме заданных), которые дадут такое же хеш-значение. Если злоумышленник может изменить не только сообщение, но и значение хеш-функции, то для дополнительной безопасности можно использовать хеш-ключ или код аутентификации сообщения (MAC). Не зная ключа, злоумышленник не сможет легко и удобно вычислить правильное хэш-значение с ключом для измененного сообщения.
Для обнаружения ошибок можно использовать любой код, исправляющий ошибки. Код с минимальным расстоянием Хэмминга d может обнаружить до d − 1 ошибок в кодовом слове. Использование кодов, исправляющих ошибки на основе минимального расстояния, для обнаружения ошибок может быть подходящим, если желательно строго ограничить минимальное количество обнаруживаемых ошибок.
Коды с минимальным расстоянием Хэмминга d = 2 являются вырожденными случаями кодов с исправлением ошибок и могут использоваться для обнаружения одиночных ошибок. Бит четности является примером кода, обнаруживающего одну ошибку.
Приложения, которым требуется низкая задержка (например, телефонные разговоры), не могут использовать автоматический запрос повторения (ARQ); они должны использовать прямое исправление ошибок (FEC). К тому времени, когда система ARQ обнаружит ошибку и повторно передаст ее, повторно отправленные данные прибудут слишком поздно, чтобы их можно было использовать.
Приложения, в которых передатчик немедленно забывает информацию сразу после ее отправки (например, большинство телевизионных камер), не могут использовать ARQ; они должны использовать FEC, поскольку при возникновении ошибки исходные данные становятся недоступными.
Приложения, использующие ARQ, должны иметь обратный канал ; приложения, не имеющие обратного канала, не могут использовать ARQ.
Приложения, которым требуется чрезвычайно низкий уровень ошибок (например, цифровые денежные переводы), должны использовать ARQ из-за возможности неисправимых ошибок с помощью FEC.
В технике надежности и контроля также используется теория кодов, исправляющих ошибки. [16]
В типичном стеке TCP/IP контроль ошибок осуществляется на нескольких уровнях:
Разработка кодов с исправлением ошибок была тесно связана с историей полетов в дальний космос из-за чрезвычайного ослабления мощности сигнала на межпланетных расстояниях и ограниченной мощности на борту космических зондов. В то время как ранние миссии отправляли свои данные в незакодированном виде, начиная с 1968 года, цифровая коррекция ошибок была реализована в форме (неоптимально декодированных) сверточных кодов и кодов Рида-Мюллера . [17] Код Рида-Мюллера хорошо подходил к шуму, которому подвергался космический корабль (приблизительно соответствующий колоколообразной кривой ), и был реализован для космического корабля Mariner и использовался в миссиях в период с 1969 по 1977 год.
Миссии « Вояджер -1» и «Вояджер-2» , стартовавшие в 1977 году, были предназначены для доставки цветных изображений и научной информации с Юпитера и Сатурна . [18] Это привело к увеличению требований к кодированию, и, таким образом, космический корабль поддерживался (оптимально декодированным по Витерби ) сверточными кодами, которые могли быть объединены с внешним кодом Голея (24,12,8) . Корабль «Вояджер-2» дополнительно поддерживал реализацию кода Рида-Соломона . Объединенный код Рида-Соломона-Витерби (RSV) позволил очень мощно исправить ошибки и позволил космическому кораблю совершить продолжительное путешествие к Урану и Нептуну . После модернизации системы ECC в 1989 году оба корабля использовали кодировку V2 RSV.
Консультативный комитет по системам космических данных в настоящее время рекомендует использовать коды исправления ошибок, производительность которых как минимум аналогична коду RSV «Вояджера-2». Сцепленные коды все больше теряют популярность в космических миссиях и заменяются более мощными кодами, такими как турбокоды или коды LDPC .
Различные виды осуществляемых миссий в дальний космос и на орбиту позволяют предположить, что попытка найти универсальную систему исправления ошибок будет постоянной проблемой. Для миссий, близких к Земле, характер шума в канале связи отличается от того, который испытывает космический корабль, выполняющий межпланетную миссию. Кроме того, по мере увеличения расстояния космического корабля от Земли проблема коррекции шума становится более сложной.
Спрос на полосу пропускания спутниковых транспондеров продолжает расти, чему способствует желание доставлять телевизионные сигналы (включая новые каналы и телевидение высокой четкости ) и IP-данные. Доступность транспондеров и ограничения пропускной способности ограничивают этот рост. Емкость транспондера определяется выбранной схемой модуляции и долей емкости, потребляемой FEC.
Коды обнаружения и исправления ошибок часто используются для повышения надежности носителей данных. [19] Дорожка четности, способная обнаруживать однобитовые ошибки, присутствовала на первом хранилище данных на магнитной ленте в 1951 году. Оптимальный прямоугольный код , используемый в записывающих лентах с групповым кодированием, не только обнаруживает, но и исправляет однобитовые ошибки. Некоторые форматы файлов , особенно форматы архивов , включают контрольную сумму (чаще всего CRC32 ) для обнаружения повреждения и усечения и могут использовать файлы избыточности или четности для восстановления частей поврежденных данных. Коды Рида-Соломона используются на компакт-дисках для исправления ошибок, вызванных царапинами.
Современные жесткие диски используют коды Рида-Соломона для обнаружения и исправления незначительных ошибок при чтении секторов, а также для восстановления поврежденных данных из неисправных секторов и сохранения этих данных в запасных секторах. [20] Системы RAID используют различные методы исправления ошибок для восстановления данных в случае полного отказа жесткого диска. Файловые системы, такие как ZFS или Btrfs , а также некоторые реализации RAID , поддерживают очистку и восстановление данных, что позволяет обнаруживать и (надеюсь) восстанавливать поврежденные блоки до их использования. [21] Восстановленные данные могут быть перезаписаны точно в то же физическое место, чтобы сохранить блоки в другом месте на том же оборудовании, или данные могут быть перезаписаны на заменяющее оборудование.
Динамическая память с произвольным доступом (DRAM) может обеспечить более надежную защиту от программных ошибок , полагаясь на коды, исправляющие ошибки. Такая память с коррекцией ошибок, известная как память с защитой ECC или EDAC , особенно желательна для критически важных приложений, таких как научные вычисления, финансы, медицина и т. д., а также для внеземных приложений из-за повышенного излучения в космосе.
Контроллеры памяти с коррекцией ошибок традиционно используют коды Хэмминга , хотя некоторые используют тройную модульную избыточность . Чередование позволяет распределить эффект одного космического луча, который потенциально может нарушить несколько физически соседних битов по нескольким словам, связывая соседние биты с разными словами. Пока сбой при одном событии (SEU) не превышает порог ошибки (например, одну ошибку) в каком-либо конкретном слове между обращениями, его можно исправить (например, с помощью однобитового кода, исправляющего ошибки), и иллюзия безошибочной системы памяти может сохраняться. [22]
В дополнение к аппаратным средствам, обеспечивающим функции, необходимые для работы памяти ECC, операционные системы обычно содержат соответствующие средства отчетности, которые используются для предоставления уведомлений при прозрачном восстановлении программных ошибок. Одним из примеров является подсистема EDAC ядра Linux (ранее известная как Bluesmoke ), которая собирает данные от компонентов с включенной проверкой ошибок внутри компьютерной системы; Помимо сбора и передачи отчетов о событиях, связанных с памятью ECC, он также поддерживает другие ошибки контрольной суммы, в том числе обнаруженные на шине PCI . [23] [24] [25] Некоторые системы [ указать ] также поддерживают очистку памяти для обнаружения и исправления ошибок на ранней стадии, прежде чем они станут неустранимыми.