Коды для исправления ошибок

Question

Мне нужно использовать метод коррекции ошибок для коротких сообщений (от 100 до 200 бит). Объем, доступный для добавления избыточных битов, ограничен 20-50%.

Мне нужно будет реализовать кодирование и декодирование в C/C++. Поэтому он должен быть либо открытым, либо достаточно простым для программирования. (У меня был некоторый опыт в прошлом с алгоритмами декодирования - они ужасны!)

Может ли кто-нибудь посоветовать подходящий код ошибки для использования (с соответствующими параметрами)?

Answer 1

Посмотрите на исправление ошибок Рида Соломона.

Пример реализации на C++ доступен here.

Для другого варианта смотрите here - смотри пункт # 11

EDIT: Если вы хотите коммерческую библиотеку - http://www.schifra.com/faq.html

Answer 2

Рида-Соломона кодеры описаны в виде RS (мощность, полезная нагрузка). Емкость всегда 2^SYMBOL-1, где SYMBOL - это количество бит в каждом символе Рида-Соломона. Довольно часто этот размер SYMBOL составляет 8 бит (обычный байт). Обычно это может быть от 3 до 16 бит. Для 8-битного символа кодер Рида-Соломона будет называться RS (255, PAYLOAD).

PAYLOAD - количество символов без четности. Если вам нужны 4 символа четности, вы должны указать RS (255,251).

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

Например, если ошибка возникает в среднем каждые 8 ​​бит, тогда 8-битный символ не подходит; почти каждый символ будет иметь ошибку! Вы можете пойти на 4-битные символы и использовать кодек RS (15,11) - до 11 4-битных символов за раз, производя 4 символа четности на блок. Чем меньше размер символа, тем ниже значение CAPACITY (например, для SYMBOL размером 4 бита, 2^4-1 == 15 символа CAPACITY).

Но обычно вы должны использовать 8-битные символы. Если у вас более реалистичная частота ошибок, например, 10% ваших 8-битных символов ошибочны, тогда вы можете использовать RS (255,205) - 50 символов четности на 255 символов «кодовое слово» Рида-Соломона с максимальным PAYLOAD 205 байт. Это дает нам 25% -ную четность, позволяющую исправить кодовое слово, содержащее ошибки до 12,5%.

Использование https://github.com/pjkundert/ezpwd-reed-solomon «S C++/ezpwd/RS Reed-Solomon API, необходимо указать это так:

#include <ezpwd/rs> 
... 
ezpwd::RS<255,205> rscodec; 

Поместите ваши данные в станд :: строки (он может обрабатывать сырые 8-разрядный двоичные данные просто отлично) или станд :: вектор и вызвать API, добавляя 50 символов четности:

std::string data; 
// ... fill data with a fixed size block, up to 205 bytes 
rscodec.encode(data); 

Отправить ваши данные, а затем, после получения данных + паритет, восстановить исходные данные (и отбросить 50 символов четности):

int corrected = rscodec.decode(data); 

Если данные могут быть восстановлены, количество исправленных символов будет возвращено или -1, если кодовое слово Рида-Соломона содержит слишком много ошибок.

Наслаждайтесь!