В теории информации и теории кодирования с приложениями в информатике и телекоммуникациях обнаружение и исправление ошибок ( EDAC ) или контроль ошибок являются методами, которые обеспечивают надежную доставку цифровых данных по ненадежным каналам связи . Многие каналы связи подвержены шуму канала , и, таким образом, ошибки могут быть внесены во время передачи от источника к приемнику. Методы обнаружения ошибок позволяют обнаруживать такие ошибки, в то время как исправление ошибок позволяет восстановить исходные данные во многих случаях.
Обнаружение ошибок — это обнаружение ошибок, вызванных шумом или другими помехами во время передачи от передатчика к приемнику.
Исправление ошибок — это обнаружение ошибок и восстановление исходных, безошибочных данных.
В классической античности переписчики еврейской Библии получали оплату за свою работу в соответствии с количеством стихов (стиховых строк). Поскольку прозаические книги Библии почти никогда не писались стихами, переписчики, чтобы оценить объем работы, должны были подсчитывать буквы. [1] Это также помогало обеспечить точность передачи текста при создании последующих копий. [2] [3] Между 7 и 10 веками н. э. группа еврейских писцов формализовала и расширила это, чтобы создать Числовую Масору, чтобы гарантировать точное воспроизведение священного текста. Она включала подсчет количества слов в строке, разделе, книге и группах книг, отмечая средний стих книги, статистику использования слов и комментарии. [1] Стандарты стали такими, что отклонение даже в одной букве в свитке Торы считалось неприемлемым. [4] Эффективность их метода исправления ошибок была подтверждена точностью копирования на протяжении столетий, продемонстрированной открытием свитков Мертвого моря в 1947–1956 годах, датируемых примерно 150 годом до н. э. — 75 годом н. э . [5]
Современное развитие кодов исправления ошибок приписывают Ричарду Хэммингу в 1947 году. [6] Описание кода Хэмминга появилось в работе Клода Шеннона « Математическая теория связи» [7] и было быстро обобщено Марселем Дж. Э. Голеем . [8]
Все схемы обнаружения и исправления ошибок добавляют некоторую избыточность (т. е. некоторые дополнительные данные) к сообщению, которую получатели могут использовать для проверки согласованности доставленного сообщения и восстановления данных, которые были определены как поврежденные. Схемы обнаружения и исправления ошибок могут быть как систематическими , так и несистематическими. В систематической схеме передатчик отправляет исходные (безошибочные) данные и прикрепляет фиксированное количество контрольных битов (или данных четности ), которые выводятся из битов данных с помощью некоторого алгоритма кодирования. Если требуется обнаружение ошибок, получатель может просто применить тот же алгоритм к полученным битам данных и сравнить его вывод с полученными контрольными битами; если значения не совпадают, то в какой-то момент во время передачи произошла ошибка. Если требуется исправление ошибок, получатель может применить алгоритм декодирования к полученным битам данных и полученным контрольным битам, чтобы восстановить исходные безошибочные данные. В системе, использующей несистематический код, исходное сообщение преобразуется в закодированное сообщение, несущее ту же информацию и имеющее по крайней мере столько же бит, сколько и исходное сообщение.
Хорошая производительность контроля ошибок требует выбора схемы на основе характеристик канала связи. Обычные модели каналов включают модели без памяти , где ошибки происходят случайно и с определенной вероятностью, и динамические модели, где ошибки происходят в основном пачками . Следовательно, коды обнаружения и исправления ошибок можно в целом разделить на коды обнаружения/исправления случайных ошибок и коды обнаружения/исправления пачки ошибок . Некоторые коды также могут подходить для смеси случайных ошибок и пачки ошибок.
Если характеристики канала не могут быть определены или сильно изменчивы, схема обнаружения ошибок может быть объединена с системой повторных передач ошибочных данных. Это известно как автоматический запрос на повтор (ARQ) и наиболее часто используется в Интернете. Альтернативным подходом к контролю ошибок является гибридный автоматический запрос на повтор (HARQ), который представляет собой комбинацию ARQ и кодирования с исправлением ошибок.
Существует три основных типа исправления ошибок: [9]
Автоматический запрос на повтор (ARQ) — это метод контроля ошибок при передаче данных, который использует коды обнаружения ошибок, сообщения подтверждения и/или отрицательного подтверждения, а также тайм-ауты для достижения надежной передачи данных. Подтверждение — это сообщение, отправляемое получателем, чтобы указать, что он правильно получил кадр данных .
Обычно, когда передатчик не получает подтверждение до истечения времени ожидания (т. е. в течение разумного периода времени после отправки кадра данных), он повторно передает кадр до тех пор, пока он не будет правильно получен или ошибка не сохранится после заданного количества повторных передач.
Три типа протоколов ARQ — это Stop-and-wait ARQ , Go-Back-N ARQ и Selective Repeat 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). Не зная ключа, злоумышленник не сможет легко или удобно вычислить правильное ключевое значение хэша для измененного сообщения.
Цифровые подписи могут обеспечить надежную гарантию целостности данных, независимо от того, были ли изменения данных случайными или злонамеренными. Цифровые подписи, пожалуй, наиболее примечательны тем, что являются частью протокола HTTPS для безопасного просмотра веб-страниц.
Любой код с исправлением ошибок может быть использован для обнаружения ошибок. Код с минимальным расстоянием Хэмминга d может обнаружить до d − 1 ошибок в кодовом слове. Использование кодов с исправлением ошибок на основе минимального расстояния для обнаружения ошибок может быть подходящим, если требуется строгое ограничение на минимальное количество обнаруживаемых ошибок.
Коды с минимальным расстоянием Хэмминга d = 2 являются вырожденными случаями кодов с исправлением ошибок и могут использоваться для обнаружения одиночных ошибок. Бит четности является примером кода с обнаружением одиночных ошибок.
Приложения, требующие малой задержки (например, телефонные разговоры), не могут использовать автоматический повторный запрос (ARQ); они должны использовать прямое исправление ошибок (FEC). К тому времени, когда система ARQ обнаружит ошибку и повторно ее передаст, повторно отправленные данные прибудут слишком поздно, чтобы их можно было использовать.
Приложения, в которых передатчик немедленно забывает информацию после ее отправки (например, большинство телевизионных камер), не могут использовать ARQ; они должны использовать FEC, поскольку при возникновении ошибки исходные данные становятся недоступными.
Приложения, использующие ARQ, должны иметь обратный канал ; приложения, не имеющие обратного канала, не могут использовать ARQ.
Приложения, требующие крайне низкого уровня ошибок (например, цифровые денежные переводы), должны использовать ARQ из-за возможности возникновения неисправимых ошибок с помощью FEC.
Надежность и контрольная техника также используют теорию кодов с исправлением ошибок. [16]
В типичном стеке TCP/IP контроль ошибок выполняется на нескольких уровнях:
Разработка кодов коррекции ошибок была тесно связана с историей миссий в дальний космос из-за чрезвычайного ослабления мощности сигнала на межпланетных расстояниях и ограниченной доступности мощности на борту космических зондов. В то время как ранние миссии отправляли свои данные некодированными, начиная с 1968 года, цифровая коррекция ошибок была реализована в форме (неоптимально декодированных) сверточных кодов и кодов Рида-Мюллера . [17] Код Рида-Мюллера хорошо подходил для шума, которому подвергался космический корабль (приблизительно совпадая с колоколообразной кривой ), и был реализован для космического корабля Mariner и использовался в миссиях между 1969 и 1977 годами.
Миссии Voyager 1 и Voyager 2 , начавшиеся в 1977 году, были разработаны для доставки цветных изображений и научной информации с Юпитера и Сатурна . [18] Это привело к повышению требований к кодированию, и, таким образом, космические аппараты поддерживались (оптимально декодированными по Витерби ) сверточным кодом, который можно было объединить с внешним кодом Голея (24,12,8) . Аппарат Voyager 2 дополнительно поддерживал реализацию кода Рида-Соломона . Объединенный код Рида-Соломона-Витерби (RSV) обеспечивал очень мощную коррекцию ошибок и позволил космическому аппарату продлить путешествие к Урану и Нептуну . После модернизации системы ECC в 1989 году оба аппарата использовали кодирование V2 RSV.
Консультативный комитет по системам космических данных в настоящее время рекомендует использовать коды исправления ошибок с производительностью, аналогичной коду RSV Voyager 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] Некоторые системы [ указать ] также поддерживают очистку памяти для раннего обнаружения и исправления ошибок, прежде чем они станут неустранимыми.