избыточная кодировка?

Question

Это скорее вопрос информатики / теории информации, нежели простой вопрос программирования, поэтому, если кто-нибудь знает лучший сайт для публикации, пожалуйста, дайте мне знать.

Допустим, у меня есть N-битный фрагмент данных, который будет избыточно отправлен в M сообщениях, где по крайней мере M-1 из этих сообщений будет успешно получено. Меня интересуют различные способы кодирования N-битной части данных в меньшем количестве бит на сообщение. (это похоже на RAID , но на гораздо меньшем уровне, где N = 8 или 16 или 32)

Пример: предположим, N = 16 и M = 4. Тогда я мог бы использовать следующий алгоритм:

1st and 3rd message: send "0" + bits 0-7
2nd and 4th message: send "1" + bits 8-15

Если я могу гарантировать, что 3 сообщения из 4 пройдут, то будет получено хотя бы одно сообщение от каждой группы. Таким образом, я могу сделать эту работу с 9 битами или меньше, вероятно, есть способ сделать это с меньшим количеством битов, но я не уверен, как.

Существуют ли какие-нибудь простые алгоритмы кодирования / декодирования, чтобы делать подобные вещи? Есть ли у этой проблемы имя? (если я знаю, как она называется, я могу ее погуглить!)

примечание: в моем конкретном случае сообщения либо приходят правильно, либо не приходят вообще (сообщения не приходят с ошибками).

(правка: перенесена вторая часть в отдельный вопрос)

Answer 1

(Ниже следует неполный ответ. Я могу добавить еще.)

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

Ваш первый вопрос просит найти код канала. Простой пример, который вы приводите, похож на код повторения , т.е. вы отправляете одно и то же сообщение более двух раз (обычно нечетное количество раз), и затем полученное сообщение чаще всего принимается как Оригинал сообщения.

Этот код неэффективен. Чтобы использовать стандартную запись, пусть k = количество бит в исходном сообщении, а n = количество бит в передаваемом сообщении. Для вашего примера k = 16 и n = 36. Мера эффективность кодирования равна k / n, где более высокий означает более эффективный. В вашем случае k / n = 0,44. Это низко.

Код повторения представляет собой простой вид блочного кода , то есть избыточность добавляется к каждому блоку из k битов, чтобы создать кодовое слово из n битов. Как и другие упомянутые коды Хэмминга и Рида-Соломона . Коды Хэмминга относительно легко понять с помощью некоторой базовой линейной алгебры.

Этих терминов должно быть достаточно для самостоятельного поиска. Удачи.

Answer 2

Я не уверен, правильно ли я понял все детали вашего вопроса, но ваша проблема явно в разработке какого-то кода с исправлением ошибок . Это обширная область информатики, и об этом написано множество тем. Начните с Википедии и посмотрите, сможете ли вы заставить какие-либо простые схемы (например, коды Хэмминга или Рида-Соломона) работать в вашем случае.

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

РЕДАКТИРОВАТЬ: Этот материал с hackersdelight.org кажется хорошим введением.

Answer 3

Вот тривиально простая схема, которая почти в два раза эффективнее вашего примера.

Вы разбили сообщение на блоки по (N / M) * 2 бита. Вместо этого разбейте его на блоки N / (M-1) -бит. (При необходимости округлите его.) Первый блок src[0] кодируется как сам: enc[0]=src[0]. То же самое для последнего блока: enc[M-1]=src[M-1]. Каждый из других блоков получает XORed со своим левым соседом: enc[i]=src[i-1]^src[i].

Префикс каждого кодированного блока с порядковым номером логического (M) бита, по существу, так же, как вы, чтобы получатель мог определить, какой из них был отброшен. (Если вы можете быть уверены, что все прибывающие блоки поступят по порядку, тогда подойдет 1-битный порядковый номер. Просто чередуйте 0 и 1.)

Для декодирования последовательно выполняйте XOR слева и справа до тех пор, пока не попадете в упавший блок. Например. src[1] == enc[0]^enc[1]. (Удаление одного из блоков конечной точки не является особым случаем - например, если первый блок отброшен, сканирование справа восстанавливает его, а сканирование слева имеет длину 0.)

Answer 4

Вы ищете код для удаления пакета. Есть только два полезных кода удаления пакетов, которые не полностью обременены патентами, и есть только одна библиотека с открытым исходным кодом для их реализации. Найдите его здесь: http://planete -bcast.inrialpes.fr / rubrique.php3? Id_rubrique = 5

Answer 5

См. коды стирания .