1625915145-22de02e41a1725ff3ee52ab4368adbc3 (843875), страница 31
Текст из файла (страница 31)
У„[Х[ У„[У[. Решение типовых примеров П р и и е р 28.1. Закодировать по методу Шениона— фэно') алфавит, состоящий из четырех символов А, В, С и 1), если вероятности появления каждого символа в сообщении равны: Р(А)=0,28, Р(В)=0,14, Р(С)=0,48, Р(О) = 0,10. Определить экономность кода, т.
е. количество информации, приходящееся на один символ. Р е ш е н н е. Располагаем символы алфавита в порядке убывания вероятностей С, А, В, О и производии последовательные разбиения на группы При первом разбиении в первую группу Нопадает С, а во вторую А, В н О, поскольку Р(С) = 0,48 и Р(А+ В+ О) = = О 52, Первой группе приписываем кодовый символ 1, а второй группе О. Аналогично из второй группы в свою " ть н рр и пЬ и 'рпр „„,,„,„, рш„„„— р„,„„,р„„, символов (алфавит), расположенных предварительно в порядке убываикя вероятностей поивлення символов, разбивают иа две группы таким образом, чтобы сумма вероятностей появления символов, входящнк в группы, была примерно одинаковой. Каждая нз групп в свою очередь также разбивается на две по такому же принципу. Операция продолжается до тех пор, пока в каждой группе не остаррется по одному символу.
Каждый символ обозначается двоичным ""Слом, последовательные цифры которого (еднннцм н нули) показывают, в какую группу попал данный символ прн очередном разбненяи.- 15 в. г. ниипдии и кр. 228 энтвопия н мнФОРмлцин !гл в 0,28 и 0,24 и кодовыми обозначениями 01 и 00. Наконец группа В+1) разбивается на В и 1у с вероятностямн О,!4 . н 0.10 и кодовыми обозначениями 001 и 000. Процесс кодирования удобно представить в виде таб"липы 18. Табл ица 18 Появлению одного из символов алфавита соответствует полная группа несовместных событий, а общее количество информации в данном примере равно энтропии алфавита. Поэтому количество информации, прихолящееся на один кодовып символ !экономность кола). равно отношению энтропии алфавита к математическому ожиданию длины кодового обоаначенив символов алфавита: — 0,48 !о8, 0,48 — 0,28 !о8, 0,28 — 0,14 1окя 0,14 — 0,10 !о8, О,!О 1 ° 0,48+2 ° 0,28+3 ° 0,14+3 О,!О 1,751 = --'у — = 0,995.
Аналогично решаются задачи 28.9 и 28.11 — 28.13. Пример 28.2. Вероятности поступления и непостуцления.сигнала на вход приемника соответственно равны а и а = 1 — а. Вследствие помех сигнал, поступивший на вхол приемника. может быть зафиксирован на выходе с вероятностью р и не зафиксирован с вероятностью !! = 1 — р, а при отсутствии сигнала на входе он может быть зафиксирован вследствие помех с вероятностью у и не зафиксирован с вероятностью у = 1 — у. Определить количество информации о наличии сигнала на входе по наблюдению сигнала на выходе.
Р е ш е н и е. Обозначим через Х случайное число сигна- лов на входе и через )' случайное число сигналов на выходе. 227 'иоличествтг янеовмлции Тогда Р(Х=О) =а. Р (У = О [Х= 1) =р, Р (У = О [ Х = О) = у. Р (У =О)=аР+пу. Р (Х =.1.) = а, Р (У = 1 [ Х = 1) = [), Р(У= 1[Х=,О)=у. Р (У = 1) = а[!+ ау, Поэтому 7 [Х[е=ар!од, +ау!од, + т а[)+ау, ар+ ат -[-и[1 [од, +ив !од, а[!+ от ар+ ау Можно также воспользоваться формулой 7„[Х[ = l„[У[ = Н [У[ — Н [У[ а средняя условная энтропия Н, [У[ = — п(0 !ои, 8+ 8 !ои, 8) — а(у !ои, у+у 1ои, у). Оба способа дают один и тот же результат. Пример 28.3.
Имеется 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна — фальшивая, отличается по весу от остальных. Каково наименьшее число взвешиваний на рычажных весах без гирь, которое позволяет Обнаружить фальшивую монету и выяснить, легче ли она. чем остальные монеты, или тяжелее? (Си. [54[) Решение. Каждая из 12 монет может оказаться фальшивой и быть при этом тяжелее или легче настояшей. Таким вбразом, имеется 24 возможных исхода, что при равной вероятности этих исходов дает энтропию сложного опыта, опредечаюшего фальшивУю монетУ. РавнУю!ода 24 = 3+ !оиз 3 = 0,477 =3+ — '=4Л8.
0,301 Каждое взвешивание имеет три исхода, чти в предположении нх разной вероятности дает. энтропию. равную 108в 3 = 1,58, !5ч где безусловная энтропия Н [У[ = — (а[1+ ау) !08, (о[1+ ау) — (ар+ ау) [од, (о[) + ау), 22В 'эитРОпия и инФОРмАция 1гд. Р Следова1ельно, минимальное число взвешиваний 'не может 1одз 24 . 4,58 быть меньше, чем — = — ' = 2,90, т. е.
оно не меньше 1Я,8=1,58= ' трех. Действительно, покажем, что при оптимальном планировании опыта потребуется ровно три взвешивания. Чтобы число взвешиваниИ было наименьшим, каждое взвешивание должно давать наибольшее количество информации, а для этого исход взвешивания должен обладать наибольшей энтропнеИ. Пусть при первом взвешнвзнии на обе чашки положено по 1 монет. Т!ри этом, как упоминалось, возможны три исхода: 1) чашки весов остзлись в равновесии; 2) перевесила правая чашка; 3) перевесн,ча левая чашка.
При первом исходе фальшивая монета находится среди 12 — 21 отложенных монет, ' и, следовательно, вероятность этого исхода равна 12 — 21 Рг =— 12 Во втором и третьем исходах фальшивая монета лежит на одной из чашек весов. Поэтому вероятности этих исходов равны 1 Рт 3 12' Чтобы взвешивание дало нзибольшую информацию, распределение вероятностей исходов должно обладать наибольшей энтропией, чему соответствует равенство всех вероятностей исходов. Отсюда 12 — 21 1 12 12' т.
е. при первом взвешивании на каждую чашку весов следует положить по 4 монеты. Далее рассмотрим отдельно случай ау, когда при первом взвешивании чашки весов остались в равновесии, и случай б), когда одна из чашек перевесила другую. В случае а) имеем 8 настоящих (заведомо не фальшивых) монет и 4 подозрительных, которые не участвовали в первом взвешивании. Для второго взвешивания мы можем положить количество иггеоемлции на правую чашку 1 ~олозрительных монет (1~(4),- а..на левую у' (1 подозрительных и 1 — 7 настоящих монет. При этом!+/~(4, так как число подозрительных монет'равно 4.
Все возможные значения 1 и у и соответствующие вероятности исходов при втором взвешивании в случае а) сведены в таблицу 19. Таблица 19 1 2 3 4 5 6 7 8 1 О 2' 1 0 1 0 'О 1 1 2 2 2 3 3 4 0,5 0,75 0 0,25 0,5 0 0,25 0 0,25 О,! 25 0,5 0,375 0,25 05 0,375 0,5 0,25 О,!25 0,5 0,375 0,25 0,5 0,375 0,5 0,452 0,320 0,301 0,470 0,452 !)М! 0,470 0,301 В этой таблице приведена также энтропия опыта, равная 7)г) = Р! !К Рг Ра !И )зз — Рз 18 Рз" Наибольшую энтропию дают опыты М 4 и 7.
Итак, имеется два равноценных варианта второго взвешивания: необ-' ходимо либо положить на одну чашку весов две подозрительные монеты, а на другую одну подозрительную и одну настоящую (опыт М 4), либо три подозрительные на одну чашку н три настоящие на другую (опыт М 7). Читатель может самостоятельно убедиться в том, что в обоих вариантах третье взвешивание позволяет решить поставленную задачу, т. е. определить фальшивую монету и выяснить, легче ли она или тяжелее остальных.
В случае б), когда при первом взвешивании перевесила одна из чашек, монеты распределяются на три группы, по 4 подозрительных, положенных на правую и левую чашки (4 «правых» и 4 «левых»), и 4 настоящих (не участвовавших в пеРвом взвешивании). Если при втором взвешивании положить на правую чашку' весов 1, «правых» и 1, «левых», а на левую чашку Л «правых»,/з «лезых» и 1, .+ га — А — ) настоящих монет н сравнить энтропии всех возне>иных вариантов, то окажется, 230 энтгопня и мнжовмлцня 1гл.
в что имеется 13 равноценных вариантов с наибольшей (одинаковой) энтропией. Любой из этих вариантов, например (,=3, г',=2, /,=1, /„=0 или 1,=1, 1,=2, /,=О, Д= 2, дает наибольшую возможную информацию и позволяет при третьем взвешивании определить фальшивую монету и выяснить, легче ли она или тяжелее остальных. Аналогично решаются задачи 28.2 и 28.5. Задачи 28.1. Прямоугольник разделен четырьмя продольными и восемью поперечными полосами на 32 квадрата. Единственная точка с равной вероятностью может находиться в одном из этих квадратов. Определить количество информации в сообщениях: а) точка находится в квадрате Ьй 27; б) точка находится в третьей продольной и первой поперечной полосе; в) точка находится в шестой поперечной полосе. 28.2, Имеется йГ монет одного достоинства, из которых одна фальшивая, несколько легче остальных.
Сколькими взвешиваниями на рычажных вжвх без гирь можно обнаружить фальшивую монету? Прв каком наибольшем И достаточно пяти взвешиваний? 28.3, Символы алфавита азбуки Морзе могут появиться в сообщении с вероятностями: для точки — 0,51. для тире— 0,31, для промежутка между буквами — 0,12 и для промежутка между словами — 0,06. Определить среднее количество информации в сообщении из 500 символов данного алфзвита, считая, что связь между последовательными символамр отсутствует.
28.4. Сложная система нзходится в одном из )ч' различных равновозможных состояний А, Состояние системы может быгь определено путем постановки контрольных опытов; результат каждого из них показывает группу состояний, в которых находится система. В одном нз опытов при состояниях,Ан Аю ..., Ал сигнал наблюдается, при состояниях Ал~м Аа+ж .... Ам — не наблюдается. При другом опыте сигнал наблюдается, если система находитсЯ в одном из состоЯний А,, Аж ..., А, (1 < Л) нли А„н А„+, ..., Ал, (г < М вЂ” л), и не наблюдается в остальных состояниях. Чему равно количество:информации в первом и втором опытах? 231 количество'инеопилции 28.5, Неисправный телевизор находится в одном из пяти различных состояний.
которым соответствуют различные виды неисправностей, Для обнаружения вида неисправности может быть проведено несколько из семи возможных проверок, при водящих при различных состояниях. телевизора к тому, что контрольная лампочка загорается нли не загорается. В приве денной таблице зто обозначено соответственно единицей или нулем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
