Я хочу добавить к этим сообщениям код исправления ошибок. Например, 16 бит «четности».
В качестве первого подхода я использую RS(6,4) вместо GF(256). Таким образом, данные обрабатываются как 4 байта, а два байта кода исправления ошибок добавлен. Насколько я понимаю, для этой конфигурации RS один байт всего 6-байтового сообщения может быть изменен (испорчен), и алгоритм декодирования RS все равно сможет восстановить исходное сообщение. (Если два байта повреждены, декодирование RS будет сигнализировать об этой неисправимой ошибке).
Итак, теоретически все 8 бит одного байта можно изменить, и сообщение все равно будет восстановлено.Но природа возможных ошибок в каждом сценарии заключается в том, что каждый бит может быть изменен с некоторой вероятностью.
Таким образом, использование RS(6,4)/GF(256) не восстановит сообщение, если будут изменены только два бита. быть изменен в некоторых случайных местах, а не внутри одного и того же байта.
Я хочу восстановить, если ЛЮБЫЕ 5 бит будут изменены.
ОБНОВЛЕНИЕ
Похоже, что Рид Соломон не подходит здесь, так:
Какой ECC использовать?
Сколько бит четности требуется?
- Размер данных — 32 бита. Есть только одно сообщение, которое будет отправлено
и более. - Существует до 15% (можно сравнить с 10%)
вероятность того, что каждый бит перевернут. - I хочу иметь возможность надежно
декодировать 32-битные данные как можно скорее. Если первый пакет
(32-битные данные + X-битная четность) поврежден без возможности восстановления, получатель
ждет следующего пакета (точно такие же данные + четность) и повторяет попытку.
Но в большинстве случаев случаев получения первого сообщения должно быть достаточно. - Декодирование может потребовать больших вычислительных ресурсов.
Я придумал следующий наивный алгоритм, основанный на этом ответе на другой вопрос:
https://stackoverflow.com/a/27865713/207717
- Добавить некоторый CRC для 32-битного сообщения (например, CRC-16 или CRC-24)
- На стороне получателя, если CRC не совпадает, выполните итерацию всеми способами, которые 1,2,3,4,5 бита можно перевернуть (это дает несколько миллионов итераций = (48 выберите 1) + (48 выберите 2) + (48 выберите 3) + (48 выберите 4)+(48 выберите 5) - Меня это устраивает.
Имеет ли это смысл? И если да - Какое максимальное количество бит я могу исправить:< /p>
- 32 бита данных + CRC-16
- 32 бита данных + CRC-24
- 322 бита data + CRC-32
В какой-то момент проверка N числа перевернутых битов приведет к коллизиям с разными допустимыми сообщениями. Это N для различных CRC?
ОБНОВЛЕНИЕ 2
Комментарий rcgldr указал мне на коды BCH.Я портировал эту реализацию https://www.eccpage.com/bch3.c на C#, чтобы провести несколько тестов с кодовым словом 48 бит, 24 битами данных, 24 битами четности и способностью исправления ошибок 4.
До 4 ошибок работает отлично, но при 5 ошибках часто ошибается - ошибка не обнаруживается и декодер думает, что декодировался успешно (строка printf("Неполное декодирование: обнаружены ошибки\n") никогда не достигается).
Итак, возникает еще один вопрос: поскольку BCH являются кодами, исправляющими ошибки, означает ли это, что они не способны обнаруживать ошибки, превышающие корректирующую способность? Или связанная реализация ошибочна?
В конце концов: как добиться возможности исправления ошибок И обнаружения? Например: уметь исправлять до 4 ошибок и обнаруживать до 7 ошибок, длина данных 24 бита, сложность декодирования не важна.
ОБНОВЛЕНИЕ 3
На данный момент у меня есть рабочий код C# BCH, переведенный отсюда https://www.eccpage.com/bch3.c
Версия C# здесь: https://codefile.io/f/NYCxFluwzE
Я до сих пор не знаю, как создать код исправления ошибок, который позволит исправлять до 4 ошибок, а затем одновременно обнаружение до 7 ошибок для моих 24 бит данных + необходимые биты четности
Подробнее здесь: https://stackoverflow.com/questions/791 ... es-like-24
