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

Question

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

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

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

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

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

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

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

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

Answer 1

См erasure codes.

Answer 2

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

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

EDIT: This material from hackersdelight.org кажется приятным знакомством.

Answer 3

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

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

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

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

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

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

Answer 4

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

Answer 5

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

Вы нарезали сообщение на блоки (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.)