Эту задачу я придумал давным-давно, когда пытался формализовать задачу о передаче информации по каналу с помехами. Итак.

Господин Вход, господин Выход и Чертик и Канал.

Вход собирается передать Выходу N бит информации.

Для этого у него есть Канал, по которому можно послать Пакет — число от 0 до X-1.

Каждый раз, когда вход посылает число, чертик прибавляет к нему свое — от 0 до Y-1.
Чертик может прибавить любое число на свой выбор, но он не знает, какие числа посылаются или посвылались.

До сеанса связи Вход и Выход догавариваются о том, каким образом Вход будет передавать информацию. Чертик подслушивает разговор и знает, как они собираются это делать.

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

Вопрос.

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

2. Передать фиксированное число бит за наименьшее гарантированное и/или матожидаемое число пакетов.

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

4. Рассмотреть частный случай X=Y=2.

Здравствуйте, mihoshi, Вы писали:

M>Вход собирается передать Выходу N бит информации.

M>Для этого у него есть Канал, по которому можно послать Пакет — число от 0 до X-1.

M>Каждый раз, когда вход посылает число, чертик прибавляет к нему свое — от 0 до Y-1.
M>Чертик может прибавить любое число на свой выбор, но он не знает, какие числа посылаются или посвылались.

Пакет ограничен N битами? X + Y <= 2^N ?

Если нет, то почему бы не воспользоваться чем-то вроде циклических кодов?

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, mihoshi, Вы писали:

M>>Вход собирается передать Выходу N бит информации.

M>>Для этого у него есть Канал, по которому можно послать Пакет — число от 0 до X-1.

M>>Каждый раз, когда вход посылает число, чертик прибавляет к нему свое — от 0 до Y-1.
M>>Чертик может прибавить любое число на свой выбор, но он не знает, какие числа посылаются или посвылались.

UgN>Пакет ограничен N битами? X + Y <= 2^N ?

UgN>Если нет, то почему бы не воспользоваться чем-то вроде циклических кодов?

X + Y < 2^N

Вопрос в том, сколько чисел послать понадобится.

Здравствуйте, mihoshi, Вы писали:

M>X + Y < 2^N

M>Вопрос в том, сколько чисел послать понадобится.

Тогда, если будем посылать максимальное X < 2^N, то г.Ч обломится, правильно?

Здравствуйте, mihoshi, Вы писали:

<>

Пусть число, которое нужно переслать, равно L.
Тогда посылаем L мусорных пакетов и все

В случае если X > Y, (X+Y)<=2^N то легко за один пакет передавать как минимум 1 бит информации:
0 <-- 0
1 <-- Y
...
k <-- k*Y

Здравствуйте, mihoshi, Вы писали:

M>Эту задачу я придумал давным-давно, когда пытался формализовать задачу о передаче информации по каналу с помехами. Итак.

M>Господин Вход, господин Выход и Чертик и Канал.

M>Вход собирается передать Выходу N бит информации.

Канал передачи данных с аддитивным шумом...мультипликативным шумом... Кодовые расстояния...
Коды исправляющие ошибки... Циклические коды... Групповые коды...
Коды Хаффмена, Рида-Соломона, Боулза-Чоудхури-Хоквингема...
Монографии, от 4 кг и выше... Кафедры... институты... диссертации...
... и прочая, и прочая, и прочая...

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, mihoshi, Вы писали:

К><>

К>Пусть число, которое нужно переслать, равно L.
К>Тогда посылаем L мусорных пакетов и все

К>В случае если X > Y, (X+Y)<=2^N то легко за один пакет передавать как минимум 1 бит информации:
К>0 <-- 0
К>1 <-- Y
К>...
К>k <-- k*Y

Верно.

Но во-первых, X не обязательно больше Y. Утверждается, что и при этом информацию передать можно.
Во-вторых, надо это сделать за минимальное число посылок.

Здравствуйте, mrhru, Вы писали:

M>>Вход собирается передать Выходу N бит информации.

M>Канал передачи данных с аддитивным шумом...мультипликативным шумом... Кодовые расстояния...
M>Коды исправляющие ошибки... Циклические коды... Групповые коды...
M>Коды Хаффмена, Рида-Соломона, Боулза-Чоудхури-Хоквингема...
M>Монографии, от 4 кг и выше... Кафедры... институты... диссертации...
M>... и прочая, и прочая, и прочая...

Разумеется, если это рассматривать в общем виде.

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

Хотя реферат я по ней таки сдавал и сдал

Здравствуйте, mihoshi, Вы писали:

M>>... и прочая, и прочая, и прочая...
M>Разумеется, если это рассматривать в общем виде.
M>Но в данной постановке это всего лишь частная задачка из теории игр. Вполне решаемая.

Тогда дополнительные вопросы:

- Из "Вход и Выход не могут никак общаться иначе как по Каналу" — следует ли, что Выход может что-либо посылать Входу?
— если — да, то влиляет ли Чёртик на обратные передачи?

— Можно ли использовать временные характеристики пакетов (время отправки, например) ?
— если — да, то можно ли рассматривать передачу данных как синхронную?
— например, аналогично методу Кодта, договорившись, что N бит сообщения будут передаваться посылками в N квантов времени,
причем, посылка — соответствует 1, отсутствие — 0?

Здравствуйте, mrhru, Вы писали:

Некоторые размышления.

> 4. Рассмотреть частный случай X=Y=2.

Т.е. алфавит сообщений и искажений -ы (0,1)

Если на Выходе пришло число 0 (2), то, очевидно, мы можем совершенно точно восстановить значение на Входе — 0 (1).
В случае значения 1, информация могла быть искажена.

0 -> 0 = 0
0 -> 1 = 0/1
1 -> 1 = 0/1
1 -> 2 = 1

Таким образом, в среднем половину бит мы можем принять точно.
И Чёртик, не зная исходного сообщения, не сможет нам помешать больше.
(Это в предположение совершенно случайного распределения входных сообщений.
Иначе Чёртик может действовать более оптимально для себя).

Здравствуйте, mrhru, Вы писали:

M>Тогда дополнительные вопросы:

M>

M> — Из "Вход и Выход не могут никак общаться иначе как по Каналу" — следует ли, что Выход может что-либо посылать Входу?
Нет.
M> — если — да, то влиляет ли Чёртик на обратные передачи?


M> — Можно ли использовать временные характеристики пакетов (время отправки, например) ?
Нет.
M> — если — да, то можно ли рассматривать передачу данных как синхронную?

M> — например, аналогично методу Кодта, договорившись, что N бит сообщения будут передаваться посылками в N квантов времени,
M> причем, посылка — соответствует 1, отсутствие — 0?

Нет. Никаких подвохов. Вся информация — последоовательность чисел. Можно считать, что Вход посылаетих блоком и Выход получает тоже все вместе (но в том же порядке).

Здравствуйте, mrhru, Вы писали:

M>Если на Выходе пришло число 0 (2), то, очевидно, мы можем совершенно точно восстановить значение на Входе — 0 (1).
M>В случае значения 1, информация могла быть искажена.

M>

M>0 -> 0 = 0
M>0 -> 1 = 0/1
M>1 -> 1 = 0/1
M>1 -> 2 = 1

M>Таким образом, в среднем половину бит мы можем принять точно.
M>И Чёртик, не зная исходного сообщения, не сможет нам помешать больше.
M>(Это в предположение совершенно случайного распределения входных сообщений.
M>Иначе Чёртик может действовать более оптимально для себя).

Подход правильный, но не доведенный до конца.
Считай, что чертик знает, что нужно передать.