Спирина, М.С. Дискретная математика

каждое из которых допускает дешифровку, и это разбиение един­ ственно. Очевидно, tii + ••• + пк= п. Алфавитное кодирование с разделимой схемой допускает де­ кодирование. Можно доказать, что префиксная схема является разделимой. Пусть задан алфавит А = {д,, ..., а„) и вероятности появления букв в сообщении: Р= {ри ..., р п}, где р, > 0 — вероят­ ность появления буквы а„ причем буквы с нулевой вероятностью появления в сообщении исключены. Для разделимой схемы а = а, Pi а л Рл алфавитного кодиро­ вания существует так называемая средняя цена, или длина коди­ рования, — это математическое ожидание длины закодированно­ го сообщ ения , которая обозначается / с и определяется как п / 0 = ^ д/(Р,)- Также эта величина служит мерой среднего удли- i=i нения слова при кодировании. Учитывая, что кодируются буквы, длина которых 1, имеем для изменения средней длины А 1а= = Хл(/(Р/)-1) = / а - Х л = / 0 -1. /=1 /=1 Рассмотрим пример. Пусть заданы алфавиты А = {х, у}, В = {0, 1} и разделимая схема о = ( х у 4 О 01 . При распределении вероятностей (0,5; 0,5) цена кодирования равна /„ = 0,5 • 1 + 0,5 • 2 = 1,5, а при распределении вероятностей (0,8; 0,2) соответственно /с = 0,8 • 1 + + 0 , 2 - 2 = 1,2. 6.5. Кодирование информации как средство обеспечения контроля работы автомата Scientia vinces —наукой победишь. Латинская формула Система контроля. Рассмотренные методы кодирования инфор­ мации обеспечивают надежное кодирование только в том случае, если ЭВМ функционирует без каких-либо нарушений. Если же появились отклонения в работе ЭВМ, повлекшие за собой ошиб­ ки при передаче и хранении информации, то пользователь ЭВМ даже не узнает об этом. Совокупность определенных методов и средств, обеспечиваю­ щих необходимое качество работы как всей ЭВМ, так и отдель­ ных ее элементов, а также автоматическое исправление возника­ ющих ошибок называется системой контроля. 312