Как передать данные через канал, когда вероятность искажения каждого бита 1/2?

На первый взгляд, никак, т.к. вероятности всех последовательностей равны.

Как...

Не изобретать «лисапед», а изучить обнаружение и исправление ошибок в теории кодирования ©

Сразу предупреждаю, что проблема меня интересует с чисто теоретической точки зрения.

Прямая теорема Шеннона © для канала с шумами:

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

«Иными словами: Для канала с помехами всегда можно найти такую систему кодирования, при которой сообщения будут переданы со сколь угодно большой степенью верности, если только производительность источника не превышает пропускной способности канала.»

P.S. Литература: 1, 2, 3, 4.

quickquest

То есть, получается существует такая схема кодирования, которая позволяет передать информацию даже по каналу где у каждого бита вероятность искажения равна 1/2?

Хорошо, пусть будет так. Теперь давайте представим, что когда один компьютер хочет передать другому сообщение состоящее из N бит(например, это письмо написанное юзером), он запускает генератор случайных чисел, который генерирует N бит случайно, после чего посылает сгенерированное генератором случайных чисел сообщение. Первый бит сообщения которое «задумал» компьютер с вероятностью 1/2 совпадёт с первым битом сообщения которое сгенерировал генератор случайных чисел и т.д. Фактически это будет эквивалентно линии связи которая с вероятностью 1/2 искажает значение каждого бита! Следовательно, если есть схема кодирования которая позволяет передачу осмысленных истинных сообщений с высокой вероятностью через такую линию, то тогда это возможно и в случае с генератором. Мы пришли к абсурду, следовательно это неверно.

есть шанс равный (1/2)^8, что в результате слепого случая значение каждого пересланного нам бита будет заменёно на противополоное. Например, если нам переслали 11111111, то мы получаем 00000000.

И здесь начинается контроль чётности.

после чего посылает сгенерированное генератором случайных чисел сообщение

fail. иди Шеннона читай

С радостью пойду. Но в чём fail?

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

каждый бит переданный через этот канал имеет шанс сменить своё значение на противоположное с вероятностью 1/2

Сдается, если получатель не имеет дополнительной информации о структуре сообщения и структура шума строго случайна, то это вариант шифрования «одноразовый блокнот», в твоей формулировке полученное сообщение принципиально нечитаемо.

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

Хотя и с понижением скорости передачи что-то не складывается. Проблема в том, что по условию ТС использует XOR исходного сообщения со строго случайным потоком шума с вероятностью 1 или 0 строго 1/2. А это, как ни понижай скорость, какое кодирование ни вводи, а один хрен «One Time Pad».

Возможно я здесь не прав.

В реальной жизни сигнал скорее суммируется с шумом, то есть для цифрового канала это эквивалентно операциям OR или AND. Тогда все маленько по другому.

Фактически это будет эквивалентно линии связи которая с вероятностью 1/2 искажает значение каждого бита!

Схема передачи по каналу с шумом (рис.11.1). Формула вероятности безошибочного приёма внизу.

Декодер анализирует не одиночные биты, а группы, обладающие свойством обнаружения и коррекции ошибок за счёт избыточности и, в пределе, может ждать бесконечное время, пока в потоке не появится группа бит (в пределе, о-о-очень длинная), которую он правильно декодирует с коррекцией ошибок.

Никак.

Если скорость передачи сообщений меньше пропускной способности канала связи

внезапно, пропускная способность такого канала равна нулю

https://ru.wikipedia.org/wiki/Теоремы_Шеннона_для_канала_с_шумами

если лень считать по формулам, можно объяснить на пальцах:

сидят два экстрасенса на расстоянии в 10000км, без средств связи. один другому телепатически передает данные: нули и единицы, вперемешку. другой на каждый бит подбрасывает монетку и записывает единицу или ноль. очевидно, вероятность искажения каждого бита = 1/2. также очевидно, что пропускная способность такого «канала» равна нулю.

fail. иди Шеннона читай

Как бы не совсем. Для проверки попытался представить канал, у которого вероятность замены бита на противоположный больше ½.

пропускная способность такого «канала» равна нулю.

Да, но обычно это называется обрыв или отсутствие канала, а ТС надеется что-то передать, т.е. можно предположить, что его вероятность 1/2 не константа, а асимптотическое значение. Например, канал может быть не эргодичен. А коли так, то при наличии бесконечного времени можно из этого извлечь ненулевую пропускную способность.

а ТС надеется что-то передать, т.е. можно предположить

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

а вы (в смысле, не ты лично, а 90% участников треда) тут ему про шеннона парите

вероятность 1/2 не константа, а асимптотическое значение. Например, канал может быть не эргодичен

каждый бит переданный через этот канал имеет шанс сменить своё значение на противоположное с вероятностью 1/2

каждый бит. 1/2

Для проверки попытался представить канал, у которого вероятность замены бита на противоположный больше ½.

представить-то можно, но такой канал (с вероятностью p>1/2) будет эквивалентен каналу с вероятностью q=1-p. т.к. p>1/2, значит q<1/2. достаточно инвертировать каждый переданный бит, чтобы полностью свести задачу декодирования p>1/2 к задаче с условием q<1/2

а канал с вероятностью искажения p=1 по пропускной способности эквивалентен каналу без искажений (q=1-p=0).

90% участников треда) тут ему про шеннона парите

Ну, это для него тоже может быть полезно.

каждый бит. 1/2
поэтому тапками чур не бить.

Предлагаю не бить его 2 тапками с вероятностью 1/2 :)

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

С точки зрения криптографии это сообщение, зашифрованное XOR'ом с идеальным one-time pad. А для такого шифра математически доказана невзламываемость.

каждый бит переданный через этот канал имеет шанс сменить своё значение на противоположное с вероятностью 1/2.

IMXO те, кто говорит, что возможно, вместо «на противоположное» прочитали «на случайное»

ЗЫ и странно, что никто ещё не вспомнил квантовую телепортацию для сверхсветовой связи.

инвертируем и получаем меньше ½, не? случай == ½, конечно, особый - его пропускная способность == 0

рис.11.1

По твоей ссылке меня встретила картинка «Бог живой и он любит тебя». Чет я стремаюсь читать, что там.

Чет я стремаюсь читать, что там.

Не боИсь. Там простая схема. А «Патрег-бог» — живой. Что не так? :)

Да, именно это я и хотел сказать.

«Иными словами: Для канала с помехами всегда можно найти такую систему кодирования, при которой сообщения будут переданы со сколь угодно большой степенью верности, если только производительность источника не превышает пропускной способности канала.»

ну так в этом конкретном случае пропускная способность канала равна, сюрприз, в точности нулю.