Чертик
От: mihoshi Россия  
Дата: 31.03.03 12:23
Оценка:
Эту задачу я придумал давным-давно, когда пытался формализовать задачу о передаче информации по каналу с помехами. Итак.

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

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

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

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

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

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

Вопрос.

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

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

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

4. Рассмотреть частный случай X=Y=2.
Re: Чертик
От: UgN  
Дата: 31.03.03 12:35
Оценка:
Здравствуйте, mihoshi, Вы писали:

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


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


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

M>Чертик может прибавить любое число на свой выбор, но он не знает, какие числа посылаются или посвылались.

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

Если нет, то почему бы не воспользоваться чем-то вроде циклических кодов?
Re[2]: Чертик
От: mihoshi Россия  
Дата: 31.03.03 12:49
Оценка:
Здравствуйте, 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

Вопрос в том, сколько чисел послать понадобится.
Re[3]: Чертик
От: UgN  
Дата: 31.03.03 12:51
Оценка:
Здравствуйте, mihoshi, Вы писали:

M>X + Y < 2^N


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


Тогда, если будем посылать максимальное X < 2^N, то г.Ч обломится, правильно?
Re: Чертик
От: Кодт Россия  
Дата: 31.03.03 13:33
Оценка: 6 (1)
Здравствуйте, mihoshi, Вы писали:

<>

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

В случае если X > Y, (X+Y)<=2^N то легко за один пакет передавать как минимум 1 бит информации:
0 <-- 0
1 <-- Y
...
k <-- k*Y
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re: Чертик
От: mrhru Россия  
Дата: 01.04.03 00:57
Оценка:
Здравствуйте, mihoshi, Вы писали:

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


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


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


Канал передачи данных с аддитивным шумом...мультипликативным шумом... Кодовые расстояния...
Коды исправляющие ошибки... Циклические коды... Групповые коды...
Коды Хаффмена, Рида-Соломона, Боулза-Чоудхури-Хоквингема...
Монографии, от 4 кг и выше... Кафедры... институты... диссертации...
... и прочая, и прочая, и прочая...
Евгений
Re[2]: Чертик
От: mihoshi Россия  
Дата: 01.04.03 04:16
Оценка:
Здравствуйте, Кодт, Вы писали:

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


К><>


К>Пусть число, которое нужно переслать, равно L.

К>Тогда посылаем L мусорных пакетов и все

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

К>0 <-- 0
К>1 <-- Y
К>...
К>k <-- k*Y

Верно.

Но во-первых, X не обязательно больше Y. Утверждается, что и при этом информацию передать можно.
Во-вторых, надо это сделать за минимальное число посылок.
Re[2]: Чертик
От: mihoshi Россия  
Дата: 01.04.03 04:19
Оценка:
Здравствуйте, mrhru, Вы писали:

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


M>Канал передачи данных с аддитивным шумом...мультипликативным шумом... Кодовые расстояния...

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

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

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

Хотя реферат я по ней таки сдавал и сдал
Re[3]: Чертик
От: mrhru Россия  
Дата: 01.04.03 04:47
Оценка:
Здравствуйте, mihoshi, Вы писали:

M>>... и прочая, и прочая, и прочая...

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

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

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

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

Евгений
Re[4]: Чертик
От: mrhru Россия  
Дата: 01.04.03 05:50
Оценка:
Здравствуйте, 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


Таким образом, в среднем половину бит мы можем принять точно.
И Чёртик, не зная исходного сообщения, не сможет нам помешать больше.
(Это в предположение совершенно случайного распределения входных сообщений.
Иначе Чёртик может действовать более оптимально для себя).
Евгений
Re[4]: Чертик
От: mihoshi Россия  
Дата: 01.04.03 10:14
Оценка:
Здравствуйте, mrhru, Вы писали:

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


M>

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


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

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


Нет. Никаких подвохов. Вся информация — последоовательность чисел. Можно считать, что Вход посылаетих блоком и Выход получает тоже все вместе (но в том же порядке).
Re[5]: Чертик
От: mihoshi Россия  
Дата: 01.04.03 10:16
Оценка:
Здравствуйте, 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>Иначе Чёртик может действовать более оптимально для себя).

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