Можно ли сделать рудиментарную коррекцию ошибок с CRC?

Question

Я знаю, что все намерение использовать CRC - это сделать обнаружение ошибок, но я слышал, как кто-то утверждает, что его можно использовать для проведения базовой коррекции ошибок в дополнение к обнаружению ошибок. Мне было любопытно, если это было так, и если так, насколько это мощно? Я имею в виду, мы обычно ссылаемся на CRC в качестве способности выполнять обнаружение X-битов, но мне интересно, если он способен выполнять коррекцию X-BIT. Если это так, как эта работа? Спасибо.

Answer 1

Можно сделать однобитный исправление ошибок с CRC. Предположим, что у одного есть CRC «Регистрация» и имеет функции для выполнения алгоритма алгоритма CRC вперед и назад немного обратно, игнорируя входящие данные

int crc_forward (int old_value, int data_bit) {if (old_value & 0x8000) return ((old_value ^ 0x8000) shl 1) ^ 0x1021 ^ data_bit; остальное возвращение (Old_Value SHL 1) ^ data_bit; } int crc_reverse (int old_value) {если (old_value & 1) return (old_value sr 1) ^ 0x8810; еще вернуть Old_Value SHR 1; }

Предположим, у одного есть пакет, который вычисляется так, что инициализация CRC к некоторому значению и запуску CRC_FORARD для каждого бита (MSB сначала) должна давать нулю. Если кто-то получает значение CRC, отличное от нуля, можно запустить алгоритм в обратном направлении (игнорируя биты данных) до тех пор, пока не будет получено значение CRC 1. Это местоположение неправильного бита.

Обратите внимание, что этот подход может быть адекватен для исправления ошибок программного обеспечения в таких вещах, как NAND Flash. Чтобы использовать его для коррекции аппаратных ошибок, нужно будет либо иметь возможность задерживать операции чтения до тех пор, пока ECC не может быть обработан, иначе любую нужна таблица значений синдрома и битовых позиций.

Answer 2

Вы можете выполнять многобитовую коррекцию ошибок с CRC. Глядя на Wikipedia, со ссылками на работу KOOPMANS, CRC может обнаружить его ошибки Hamming_Distance-1. Расстояние гамма зависит от длины полезной нагрузки, а также многочлена использования CRC. Таким образом, например, Коопманцы полинома 0xBA0DC66b могут обнаруживать до 5 битов ошибки в сообщениях до 16360 битов длиной. Алгоритм, описанный в предыдущих двух сообщениях, может быть продлен до многих битов по мере необходимости, но время расширяется экспоненциально с количеством битов для исправления.

1. Рассчитать ошибку CRC = CRC_GOTORT ^ CRC_EXPED.
2. Просмотрите все возможные 1-битные сообщения (т.е. все 0s, A 1 и все 0s) (есть чехлы Message_Length для оценки. Примечание Это биты, а не байты), и бит ошибки - это сообщение, которое генерирует ошибку CRC.
3. Переверните обнаруженный бит, чтобы исправить ошибку.

Если вы не можете найти 1 бит, соответствующую ошибку CRC, просмотрите все 2-битные, 3-битные до вашего Hamming_Distance-1. Обратите внимание, что это становится медленным быстрым, Message_Length в квадрате для 2 битов, кулочны для 3 битов до пятой мощности на пять битов.

Answer 3

Я недавно работал над обнаружение ошибок CRC16 и коррекцию одной битной ошибки.

Вот основная идея:

1. Предположим, у вас есть одна битовая ошибка.
2. Если данные + CRC не включают ошибку, CRC будет 0, а не нет.
3. Мы определяем CRC, отправленные как CRC и CRC, полученные в качестве КГР.
4. Тогда биты ошибок даны CRCox = CRCs ^ CRCr.
5. Результатом охватывает как ошибки CRC, так и ошибки данных.
6. Посмотрите на какую связь между CRCOX и ошибкой бит.

Это понятно? У меня есть бумага об этом. Если вы хотите узнать больше, просто дайте мне знать.