Большая Советская Энциклопедия (КО)

  энтропия источника. Граница для L в формуле (1) может не достигаться. Однако при любых p_i существует метод К. (метод Шеннона — Фэно), для которого

  L £ Н + 1. (2)

  Метод состоит в том, что сообщения располагаются в порядке убывания вероятностей и полученный ряд делится на 2 части с вероятностями, по возможности близкими друг к другу. В качестве 1-го двоичного знака принимают 0 в 1-й части и 1 — во 2-й. Подобным же образом делят пополам каждую из частей и выбирают 2-й двоичный знак и т.д., пока не придут к частям, содержащим только по одному сообщению.

  Пример 1. Пусть n = 4 и p₁ =9/16, р₂ = р₃ = 3/16, p₄ = 1/16. Применение метода иллюстрируется табл.:

B данном случае L =

  Задача о «сжатии» записи сообщений в данном алфавите (то есть задача об уменьшении избыточности) может быть решена на основе метода Шеннона — Фэно. Действительно, с одной стороны, если сообщения представлены последовательностями букв длины N из м -буквенного алфавита, то их средняя длина L_N после К. всегда удовлетворяет неравенству L_N ³NH/log₂ т, где Н — энтропия источника на букву. С другой стороны, при сколь угодно малом e>0 можно добиться выполнения при всех достаточно больших N неравенства

  С этой целью пользуются К. «блоками»: по данному e выбирают натуральное число s и делят каждое сообщение на равные части — «блоки», содержащие по s букв. Затем эти блоки кодируют методом Шеннона — Фэно в тот же алфавит. Тогда при достаточно больших N будет выполнено неравенство (3). Справедливость этого утверждения легче всего понять, рассматривая случай, когда источником является последовательность независимых символов 0 и 1, появляющихся с вероятностями соответственно р и q, p ¹q. Энтропия на блок равна s-кpaтной энтропии на одну букву, т. е. равна sH =s (plog₂ 1/p+qlog₂ 1/q ). Кодовое обозначение блока требует в среднем не более sH + 1 двоичных знаков. Поэтому для сообщения длины N букв L_N £(1+N/s ) (sH +1) = N (H +1/s ) (1+s/N ), что при достаточно больших s и N/s приводит к неравенству (3). При таком К. энтропия на букву приближается к своему максимальному значению — единице, а избыточность — к нулю.

  Пример 2. Пусть источником сообщений является последовательность независимых знаков 0 и 1, в которой вероятность появления нуля равна р =³ /₄ , а единицы q =¹ /₄ . Здесь энтропия Н на букву равна 0,811, а избыточность — 0,189. Наименьшие блоки (s = 2), то есть 00, 01, 10, 11, имеют соответственно вероятности р² = ⁹ /₁₆ , pq = ³ /₁₆ , qp = ³ /₁₆ , q² =¹ /₁₆ . Применение метода Шеннона — Фэно (см. пример 1) приводит к правилу К.: 00®0, 01®10, 10®110, 11®111. При этом, например, сообщение 00111000... примет вид 01111100... На каждую букву сообщения в прежней форме приходится в среднем ²⁷ /₃₂ = 0,844 буквы в новой форме (при нижней границе коэффициента сжатия, равной Н = 0,811). Энтропия на букву в новой последовательности равна 0,811/0,844 = 0,961, а избыточность равна 0,039.

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

  Ю. В. Прохоров.

Кодированный оригинал

Коди'рованный оригина'л, издательский машинописный оригинал, закодированный обычно в форме 6-дорожечной перфорированной ленты, которая служит программой для автоматического набора. К. о. подготавливается на печатно-кодирующих устройствах (ПКУ), включающих буквопечатающий аппарат (обычно электрифицированную пишущую машинку), электронный счетный блок, кодирующий аппарат (ленточный перфоратор), устройство для автоматической печати с перфоленты и пульт управления, на котором устанавливаются гарнитура и кегль шрифта, формат набора, размер абзацного отступа, количество строк на полосе и т.п. При печатании издательского оригинала на пишущей машинке автоматически в перфораторе на бумажной ленте пробиваются отверстия, расположение и число которых соответствует коду напечатанного знака. Одновременно в счётном устройстве учитывается ширина каждого печатающего и пробельного элемента для формирования строки набора.

  Могут быть использованы буквопечатающие аппараты, оснащенные шрифтом, сходным по рисунку с типографским (наподобие наборно-пишущих машин с переменным шагом каретки), для подготовки масштабных К. о., для которых помимо построчного совпадения, характерно графическое сходство с наборной полосой по размерам и пропорциям. Масштабные К. о. могут быть напечатаны с выровненным правым краем, что еще больше усиливает сходство с оттисками, изготовленными с набора. Масштабные К. о. целесообразны для изданий с рисунками в оборку, а также для отдельных встречающихся в издании сложно оформленных страниц (разворотов). Применяются также оригиналы с неполнокодовой лентой, то есть без разделения кодированного текста на строки. Неполнокодовая лента преобразуется на специальных устройствах (автоматических и полуавтоматических) в полнокодовую ленту, пригодную для управления работой наборного автомата, или используется без преобразования, если наборные автоматы оснащены для этой цели специальными устройствами. Основное преимущество неполнокодовой ленты: упрощение первичного кодирования и повышение производительности более чем в полтора раза.

  Программирование набора, осуществляемое одновременно с печатанием оригинала в издательстве исключает необходимость повторения клавиатурного процесса для подготовки программы автоматического набора в типографии, что является главным условием эффективного использования современной быстродействующей техники автоматического набора. Вместе с тем оно обеспечивает высокую степень идентичности оригинала и набора. Построчное соответствие между текстом К. о. и набором даёт возможность издательству осуществить корректуру при подготовке издания к производству в донаборной стадии, не прибегая к корректурному обмену между издательством и типографией, и тем самым создает условия, необходимые для выпуска изданий в типографии по непрерывно-сквозному графику, и сокращает продолжительность прохождения их в производстве в 2—4 раза по сравнению с обычными способами набора. К. о. находит всё большее применение в издательствах СССР и других стран.

  Лит.: Эйдельнант И. Б., Автоматизация набора и издательская корректура, М.. 1963; его же, Кодированный издательский оригинал для автоматического набора, М., 1965; Берлин А. С., Системы программирования набора, М., 1971.