Какие методы можно использовать для кодирования данных в одностороннем канале с потерями?

Question

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

Но вам все равно нужно отправлять данные через него.Какие методы можно использовать для отправки цифры и текст по этому каналу?

1. Можно ли закодировать числа так, чтобы даже при случайном изменении битов их можно было интерпретировать как значения, близкие к оригиналу (с потерями передача)?

2. Есть ли способ отправить строку символов (скажем, ASCII) в без потерь мода?

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

Answer 1

В зависимости от некоторых подробностей о вашем канале с потерями, которые вы не предоставили, я бы рекомендовал сначала использовать Код Грея чтобы гарантировать, что однобитовые ошибки приводят к небольшим различиям (чтобы удовлетворить ваше желание уменьшить потери при передаче с потерями), а затем, возможно, также закодировать полученный поток с помощью некоторого «без потерь» (==пытается чтобы быть без потерь ;-) кодирование.

Рид-Соломон и его варианты особенно хороши, если ваши эпизоды шума склонны возникать небольшими пакетами (несколько битовых ошибок, скажем, в одном байте), что должно хорошо взаимодействовать с кодированием Грея (поскольку многобитовые ошибки являются убийцами «потерь аспект «смягчения» Грея, предназначенный для корректного снижения качества однобитовых ошибок в сети).Это потому, что RS по своей сути является блочной схемой, и с точки зрения RS, несколько ошибок в одном блоке по сути то же самое, что и одна ошибка в нем ;-).

R-S особенно хорош, если многие ошибки стирания Проще говоря, стирание — это символ, который, скорее всего, был искажен при передаче, НО для которого вы ДЕЙСТВИТЕЛЬНО знаете тот решающий факт, что он был искажен.Физический уровень, в зависимости от того, как он спроектирован, часто может иметь подсказки об этом факте, и если есть способ сообщить об этом более высоким уровням, это может оказать решающую помощь.Позвольте мне немного объяснить стирание...:

Скажем для упрощенного примера, что 0 отправляется как уровень -1 вольт, а 1 отправляется как уровень +1 вольт (относительно некоторой опорной волны), но есть шум (физический шум часто можно хорошо смоделировать, спросите любой грамотный инженер связи;-);в зависимости от модели шума декодирование может заключаться в том, что все значения от -0,7 В и ниже считаются 0 битами, все значения +0,7 В и выше считаются 1 битами, все, что находится между ними, считается стиранием, т. е. сообщается более высокому уровню. что рассматриваемый бит, вероятно, был поврежден при передаче и поэтому его следует игнорировать.(Иногда я привожу это как один из примеров моего тезиса о том, что иногда абстракции ДОЛЖНЫ «протекать» — контролируемым и продуманным образом:следствие Мартелли из Спольского Закон дырявых абстракций!-).

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

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

На самом деле я бы не назвал всю эту область «информатикой»:Когда я закончил обучение (MSEE, 30 лет назад), я в основном пытался избегать «CS» в пользу проектирования микросхем, проектирования систем, передовых радиосистем и т. д. — тем не менее, меня учили этому материалу (ну, подмножеству, которое уже было в сфере практического инженерного использования ;-) вполне.

И просто чтобы подтвердить, что за одно поколение ситуация не сильно изменилась:моя дочь только что получила степень магистра в области телекоммуникаций (со специализацией в области передовых радиосистем) — она не может разработать ни одной серьезной программы, алгоритма или структуры данных (хотя она прекрасно справилась с обязательными курсами по C и Java, ни на этих курсах, ни где-либо еще в ее учебной программе не было абсолютно никакой глубины компьютерной науки – ее ежедневный рабочий язык матлаб...!-) -- однако она знает о теории информации и кодирования больше, чем я когда-либо узнал, и это до любое обучение на уровне доктора философии (она остается на докторскую степень, но это еще не началось).

Итак, я утверждаю, что эти области скорее EE-y, чем CS-y (хотя, конечно, границы всегда размыты - свидетельством тому является тот факт, что после нескольких лет разработки чипов я более или менее случайно оказался программистом, и так же поступали многие мои современники ;-).

Answer 2

Этот вопрос является предметом теории кодирования .

Answer 3

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

Answer 4

• Здесь избыточное кодирование, используемое в оптических носителях который может восстановить потерю битов.
  • ЕСС также используется в жестких дисках и оперативной памяти
• А TCP протокол может справиться с большой потерей данных при повторной передаче.

Answer 5

Либо турбо-коды , либо Коды проверки на четность низкой плотности для общих данных, поскольку они ближе всего подходят к приближению к пределу Шеннона - см. википедию.

Answer 6

Вы можете использовать коды Рида-Соломона .

Answer 7

См. также протокол скользящего окна (который используется TCP).

Хотя это включает в себя работу с переупорядоченными или потерянными пакетами, что не входило в определение вашей проблемы.

Answer 8

Как говорит Алекс Мартелли, в мире существует множество теорий кодирования, но коды Рида-Соломона - определенно приятное место. Если вы действительно хотите что-то построить, Джим Планк написал хороший учебник по кодированию Рида-Соломона . Планка имеет профессиональный интерес к кодированию с большим практическим опытом, чтобы поддержать это.

Answer 9

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