Один бит сломал, другой потерял: задачка по передаче данных
Комментарии (11)
mwizard
2 июля 2017 в 23:11
0↑
↓
Все уже придумано до нас.
augur
2 июля 2017 в 23:29 (комментарий был изменён)
0↑
↓
Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.
-
mwizard
2 июля 2017 в 23:48
0↑
↓
Поправлять не буду, вы правы.
3 июля 2017 в 01:29
0↑
↓
Пусть 1 бит сломан и 1 потерян. Берём код, корректирующий искажение 2 бит. А затем в полученный пакет последовательно втыкаем единичку в разные места пока алгоритм коррекции не исправит двойную (или одинарную если потеряна единичка) ошибку. Или вообще не скажет что все хорошо ибо потерянный бит был сломанной единичкой:-)
2 июля 2017 в 23:31
+2↑
↓
Под словом «теряет» (в противовес «ломает») вы подразумеваете, что на приемной стороне в среднем будет приходить 19 бит вместо 20 и место потерянного бита неизвестно?-
augur
2 июля 2017 в 23:36
0↑
↓
Совершенно верно! Сейчас уточню это в описании.
2 июля 2017 в 23:57
+2↑
↓
Весьма нетрадиционный канал. Да и по качеству паршивый. Лучше бы выкинуть его в помойку и спать пойти ;)
Не приходилось сталкиваться с подобным, первое что интуитивно хочется — наколхозить что-нибудь, чтобы детектировать пропадание бита и возвращать его обратно на место (любым значением). Типа банального дублирования как у вас или манчестера по 4 отсчета (для лучшего выделения границ), сверху обложить уже стандартным коррекционным кодом. Беда в том, что по условию задачи (неявно) возможно выпадание и двух и трех и более бит подряд с некоторрой ненулевой вероятностью (в зависимости от закона распределения). И как с этим бороться не вполне понятно. Не исключаю, что и действительно все уже придумано до нас, но где и кем — не в курсе…3 июля 2017 в 00:57
0↑
↓
Любой канал с линией клока. SPI, I²C, например.
Labunsky
3 июля 2017 в 02:08 (комментарий был изменён)
0↑
↓
К какому значению оверхеда нужно стремиться-то хоть?
А за развлечение спасибо)3 июля 2017 в 02:15
0↑
↓
Можно попробовать оценить нижную границу оверхеда.
Первое — задать BER (пусть будет 1e-6), второе — определиться с размером блока и максимальным количеством бит, которые можно потерять или исказить. Логично, что кодовые слова должны быть сильно больше 20 бит. Например, для блока из 200 бит для поддержания указанного BER нужно допустить потерю 25 бит и искажение 25 бит.
Будем бороться с проблемами по очереди и начнём с потери бит. В этом случае исходный блок будет иметь размер 175 бит и до 25 бит могут быть вставлены в произвольные места. Вопрос в том, какой максимальный размер информации при этом можно передать. Число возможных вставок ноликов и единиц огромно и примерно равно 2^131 комбинаций (sum{k = 175}^{k = 200} C^{k}{200} 2^k). То есть на полезную информацию остаётся всего 44 бита. Учитывая, что redundancy для исправления искажения битов надо накладывать не на эти 44 бита, а на исходные 175 бит, всё плохо — в BER не укладываемся. Нужно брать более длинный блок.
Пусть блок — 1000 бит, тогда для достижения указанного BER будет допустима потеря и искажение по ~90 бит. Аналогично получаем около 520 бит избыточности на чистые 910 бит. Накладываем Рида-Соломона (+180 бит), получаем 910 — 520 — 180 = 210 бит полезных данных. Если увеличивать размер блока, можно ещё увеличить долю полезных данных, но считать сложно.
P.S. На самом деле это идеальный случай. Код, допускающий вставку произвольных бит, ещё нужно придумать. Ну и предполагалось, что все события являются независимыми.
neco
3 июля 2017 в 07:03
0↑
↓
код манчестера не?
