Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 27
Текст из файла (страница 27)
Этот пример представляет различные равномерные коды, используемые для буквопечатающего телеграфнровапия с помощью телеграфных аппаратов, снабженных чрегистраь<и». Число букв в алфавите болыпинства языков не превышает 32. Поэтому можно передавать любые телеграммы, записанные буквами, с помощью 5-разрядйого двоичного кода (так как 2'=32).
Однако помимо букв в телеграммах всгречаются иногда цифры и знаки препинания, так что общее количество знаков чалфавита» телеграфного аппарата существенно больше, чем 32. Поэта»<у примитивное кодирование равномерным двоичным кодом потребовалз бы применения шести символов в кодовой комбинации. Среднее количество символов, приходящихся иа знак, существенно сокращается путем применения системы регистров. В простейшем случае телеграфный агшарат имеет два регистра, т.
е. два возможных состояния. В первом состоннии (буквенном регистре) передаются и применяются 5-разрядные кодовые комбинации, соответствующие обычным буквам алфавита н пробелу между словами. Во втором состолнии (цифровом регистре) те же кодовые комбинации соответствуют цифрам и знакам препинания.
Две кодовые комбинации используются для перевода приемного аппарата с одного регистра иа другой *. Легко убедиться, что если бы все знаки (включая цифры и знаки препинания) появлялись в телеграммах с равной вероятностью, то применение системы регистров дало бы не экономию, а, наоборот, некоторый проигрыш по сравненичо с применением прн- митнвпого б-разрядного кода. Лейс<внтельно, если вероятность того, что очередной передаваемый знак принадлежит к буквенно><у регистру, равна <(з, то вероятность того, что ровно й знаков подряд будут принадлежать к буквенному регистру, после чего появится знак, принадлежащий к цифровому регистру, равна ('/»)ь Чч=- =-2 †"+'>.
То гке самое относится и к вероятности того, ччо ровно й знаков подрнд будут принадлежать к цифровому регистру. Математическое ожидание Е числа знаков, йдупв>х подряд до смены регистра равно 2 й =-- ~; й 2-(ь+<) = ч 2 == 2. з=. < 2 ) Поэтому в среднем через каждые 2 информационных анака будет передаваться знак перевода регистра.
Ллл передачи й> знаков потребуется в среднем помимо бй> символов длл самих кодовых комбинаций еше 5Ф(2 символов для комбинаций перевода реги. 1 стра. Среднее число симвзлов на знак будет равно 5 [ ( + —,)= 2) =7,5, т. е. больше, чем при примитивном кодярованнн 6-разрядным кодом. В действительности, в текстах телеграмм цифры и знаки препинания появляютсл зна в<тельно реже, чем буквы. К тому же ш>фры часто следуют подряд одна за другой. В результате средняя данна последовательности знаков, принадлежащих к одному регистру, значительпэ больше двух н обычно достигает нескольких десятков.
В силу этого среднее число символов на один анак оказывается лишь ле намного больше пята, т. е. применение регистров дает заметную экономию. Закегим, что применение регнсгров как и другие методы сокращения избыточности, понижает помехоустойчивость. Это выражается в тон, гго оц<ибочный прием комбинации перевода регистра как знака, н,чи наоборот, вызывает ошзбки;в ряде последующих знаков и лаже изменяет число принлтых знаков. Поэтому в современных системах передачи дискретных сообщений, к которым предьявляетсл требование высокой верности, регистровое кодирование, как правило, не применяется.
4 (к й 2.7 н 2.8). Простейп>нм способом корректирую<цего кодирования является повторение информационных символов. Если каждую й-разрядную комбинацию примитивного кода повторять <( раэ, то получится корректирующий код с п=<(й и с хемминговым расстоянием <(. Интересно атметитьь что этот кад будет систематическим н циклическим. Он по общему правилу позволяет обнаружить ошибки, если нх число не превышает <( — 1, илн исправлять ошибки, если 1 их кратность (при нечетном <() ие больше 2 (г( — 1). Исправление ошибок здесь производятся по правилу большнвства, ыа в симметричном постоянном канале соответствует критерию иаксицальнаго 1 правдоподобия.
Избыточность такого кода г„== ! — — 1 значительно <1 больше, чем у более сложных кодов с таким же кеммпнговым рас- 137 стоянием. Этот недостаток лишь в релких случаях ггкупается простотой деколирования. В частном случае, если комбинации примитивного кода передается дважды, то получается кад с г(ива=2, позволшащий только обнаруживать одиночные ошвбки (а также другие ошибки нечетной кратности) прл избыто'шости гт=1/2. Можво легко построить двоичный код с такой иге избыточностью, но с г/ива=4, позволяющий исправлять аднночные ошибки и сверх того обнаруживать двойные. /(ля этого достаточно при повторении кодовой комбинации, если исходная комбинация имеет нечетный вес, инвертировать символы (т.
е. заменить О на ! н наоборот). Влила исходной комбинации должна быть не менее четырех. Лекодированне осуществляется почти так же, как и при обычном повторении. Если повторять несколько раз комбинации избыточного кода с минимальным хемминговым расстоянием г/г, то полу пггсн код с г(нт =г/гг(з, где пге — число повторений. Так, повторяя дважды комбинации с г/г=2, получим код с г(ива=4 и смогкем таким образом, исправлять одиночные ошибки н обнаруживать двойные. Сущность таких методов кодирования не изменится, если длину повторяемого блока увеличвть до длительности целого законченного сообщения.
При этом эффективность кода может повыситься благодаря делорреляции ошибок. Поэтому нельзя, как эта делают некоторые авторы, противопосташгггть системы с повторением системам с корректирукяцим кодом. Повторение сообщения — это тоже корректирующий код, мало эффективный, но зато легко реазизуечый. 6 (к $2.7 и 2.8). Говоря об ограниченных возможностях обеспечения высекай верности в каналах с шумами путем применения корргктируюпгих кодов с большой длиной блока и, мы имели в виду, в первую очередь, трудности кодирования и декодирования. В некоторых случаях, однако, возникают препятствия другого характера, ограничивающие величвну гг, а тем самым н достижимую верность Ирн лл 1 проходит заметное время между началом и концом приема блока. Но до окончания приема блока нельзя приступить к его декодированию.
Таким образом, между началом приема сообщения и выдачей его получателю происходит пепзбе>кная задержка врсиени. пропорциональная л. Если сообгцения создаются источником с фиксированной скоростью, то почти такая же задержка происходит и при кодировании, поскольку кодовая комбинапня может быть сфарчирована лишь после того, как источник выдаст лосгатачный обьем сообщения. В некотарыт системах большая задержка иеашгустнма, поскольку передаваемая информация быстро теряет свою пенность. 6 (и в 2.8). Формула (2.61) явлнется точной, если состояние капала пзвешпо обоим корреспондентам В общем случае лля неалнороапого капала скорость пеэедачи информации /'(у', у) может быгь найдена из полученной /г Н.
Колмогоровым [36] формулы «услоаггой цнфсрмацииж /' ((у', 5), у) =- /' (д', у) + [/ (5 У[у )]у' где 1'((у', 5), у) — скорость передачи информации о последовательности у' и состоянии канала 5, содержащейся в последовательности у; [/'(5, у[у')]т.
-- средняя по всем значениям у' скорость передачи информация о сосгоянии канала, содержа. щейся в последоватеньцости у, когда значения у' известны; [Г(д', у[5)[з — средняя по всем состояниям 5 скорость передачи информация а последовательности у, содержащейся в у', когда состояния канала 5 известны, Очевндгга, что состояние капала 5 нс зависит от передаваемой последовательности у, вследствие чего г'(5, у) =О. С учетом этого из (2.73) следует, что /' (у', у) = [/'(у' у[5)/з — [/' (5. у[у'Нэ' (2 74) Так как [/'(5, У[у')1„, ~ ~О (поскольку средняя скорость переда'ги ивбюрмацнв пе может быть отрицательной), получим / (д, у)С [/ (У, У[5)]з.
С другой стороны, в теории информации доказывается, что [/'(5, у[/г')]; ==/'(5* 5) =-//'(5), где //'(5) — эвтропия состояний канала, откуда следует / (у, у) ~ [/ (у; у[5)]з — // (5). Сгбьедиггяя полученные неравенства, найдем [/ (У, д[5Н, — // (5) ~ / (У', У) - [/ (У . У[5)]з. (2.76) Пусть р(у) — распределение вероятностей символов, максвянзирующее величину /'(у', у). Тогда пропускная способность канала с памятью С, = тпах/' (у', у) = — — /' [у', у[р(УЦ, (2.76) л (э) и так как неравенство (2.76) справедливо при любом распределении У(У). то С„~(/' [у', у[5, /г(у)])зч-шах [/'(У', у(5),.з. (2.77) л(И Но максимум среднего значения нескольких величин не превосходгп среднего значении максимумов, откуда (2.73) =/'(5, у)+[/'(у' у[5] 138 С, тСпгах [/'(у', у[5)]з «(шах/'(у', у[5)]з — — Сз, (2.78) лйл луб 139 (з — 'срелнениая по состояниям 5 пропускная способность канала, вычисленная в прелположенан, что состояння известны. п оисхознт резко, Если число состовний не веляко н смена их р то Н'(8) СЕ(р', 9), и из (2.75) следует приблюкенное равенство С =Ею (2.79) 2.58).
откуда лля случая двух состояний вьггекает (2.5 ). В работе [4!) показано, что прн некоторых дополнительных условиях (2.79) переходит в точное равенство. Литература 1. Ш е н н он К. Математическая теория связи. В сб. «Работы по теории нпфорчаппн н киберпепнге», Иэл-во ппостр э, - ппос анной лите ратуры„ 1963. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
