Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 13
Текст из файла (страница 13)
Однако прн математическом исследованин дискретного канала обычно отвлекаются от непрерывного канала и действующих в нем помех и определяют дискретный канал, задавая алфавит кодовых символов иг(1=1, .. м пг), поступающих на его вход, алфавит кодовых символов у'г(1=1...маг'), снимаемых с его выхода, количество о кодовых символов, пропускаемых в единицу времени, и значения ве- 62 Рнс. 2.1. Системз связи с лнскретнмм каналом.
Если вероятности перехода р(у';/уо) для каждой пары г, 1 остаются постоянными и не зависят от того, канне символы передавались и принимались ранее, то дискретный канал называется ггостоянным или однородным. Иногда применяют также другие названия: канал без памяти пли канал с независимыми оишбками. Если же вероятности перехода зависят от времени или от имевших место ранее переходов, то канал называют неоднородньгм или каналолг с памятью. В канале с памятью вероятностные связи, по крайней мере в первом приближении, распространяются только на некоторый конечный отрезок. Это значит, что вероятности перехода р(у';/уо) зависят от того, какие переходы имели место при передаче предыдущих йсимволов, н не зависят от более ранних переходов. Такой канал можно рассматривать, как имеющий ряд диск етсостояний 5„..
м 5т определяемых предыдущими р тпереходами, причем г((пггп')ь. для каждого состояния 5 определены условные вероятности переходов р»(у';(уг). В то же время лишь последние й переданных ипни ринятых символов определяют состояние канала 5 . С е ни р дние безусловные вероятности переходов опреде» ля ются гутем усреднения условных вероятностей по всем состояниям канала: е р(у г]гуо) — 1»р Ь у(уо) (2.1) »=г где Р» — вероятность состояния 5». В реальных каналах прн поэлементном приеме вероятности переходов р(у Ъг>) не являются заданными, а определяются, с одной стороны, помехами и искажениями сигналов в канале, с другой стороны, скоростью подачи кодовых символов и и первой реша>ощей схемой.
Выбирая на основании того или иного критерия оптимальну>о решающую схему, можно изменять в желательном направлении вероятности перехода. Таким оГ>- разом, для того чтобы рассматривать канал как дискретный, нужно выбрать первую решающую схему и, учитывая действующие в канале помехи и искажения, вычислить вероятности переходов. Очевидно, что в тех случаях, когда параметры реального канала постоянны и действу>ощие в канале помехи представляют стационарный случайный процесс, его дискретным отображением является постоянный канал. Если же эти условия не выполнены, то дискретным отображением, как правило, оказывается канал с памятью.
Если в канале алфавиты на входе и выходе одинаковы и для любой пары 1~1 вероятности у(у';/уг)= =ув=сопз1, то такой канал называется симметричным. Переменный канал будем также называть симметричным, если в каждом состоянии 5ч для любой пары (чЧ выполняется условие р, Я )у,) — р — сопз1(г, 1). (2.2) Очевидно, что из (2.2) следует также р(у';/ув) =сопз1, (2.3) однако обратное утверждение было бы неверным.
Каналы с памятью, в которых вь>полняется (2.3), но (2.2) не выполняется или выполняется не для всех д, будем называть симметр>рчными в среднем. Вероятности переходов в симметричном канале схематически показаны на рис. 2.2. Среди каналов, в которых алфавиты на входе и выходе неодинаковы, интерес представляет так называемый стирающий канал, в котором т'=т+1. Это название дано ему потому, что наряду с символамн уь ..., ...,у общими для входного и выходного алфавитов, выходной алфавит содержит дополнительный символ у' +ь обознача>ощий «стирание». Появление у' +> на выходе означает, что переданный символ искажен помеб4 хами и не может быть опознан.
Таким об п ннятой к разом, часть той. Р одовой последовательности оказывает тся стерстн а> Как будет показано в дальнейшем, введение р ощего символа не нарушает возможности п а- такого вильного декодирования ности праприпятой, кодовой после- Р> дователыюсти, а, наоГ>оу> У( Р> у,' Уг Р 'Рг Уг У' Рт 'Рг 'Рг г рис 23 >Вероятн ти иерехо дов в симметричном канале со стиранием. Рис, 2,2. Вероятности переходов в симметричном двоичном ивнвле. рот, облегчает ее при рациональном выборе метода кодирования и решающих схем.
Заметим, что алфавит кода на выходе определяется выбором первой решающей схемы и поэтому считается заданным лишь потому, что мы рассматриваем дискретное отображение канала. Выбор первой решающей схемы также в значительной степени определяет свойства симметрии канала. Вероятности переходов в симметричном стирающем канале показаны на рис. 2.3. 2.2. П п ро усккая способке>сть дкскратиага какала баз шумов волов г на Если в дискретном канале алфавиты кодовых с входе и у' на выходе одинаковы н х сим- (1 при с= >', (О при гф), т. е символы такой ка на выходе и входе всегда совпада ют, то 3 — 2447 нал называют дискретным кана. б лом ез шумов.
вз Он полностью характеризуется основанием кода тп и количеством символов о, пропускаемых в среднем в единицу времени. В таком канале количество информации 1(д, д'), содержащееся в принятых символах д' относительно переданных символов д, всегда равно энтропии источника Н(д). Это следует из того, что ((д, д') =Н(д) — Н(д~д')=Н(д) так как Н(д/д') =О, поскольку при известном значении д' событие д определено однозначно. Пропускная способность С дискретного канала без шумов, равная, по определению, максимальному значению ?7(д, д'), достигается в том случае, когда на вход канала поступают символы с максимальной допустимой скоростью о от источника„имеющего максимальную энтропию Н(д).
Для этого необходимо и достаточно, чтобы источник выдавал символы алфавита обьемом и> с равными вероятностями и независимо друг от друга. При этом в соответствии с (1.8) Н„„„(д) =)оя пт и, следовательно, (2А) С=он„„,(д) = )г?г ?и. Теорему кодирования для дискретного канала без шумов в случае источника с управляемой скоростью можно сформулировать следующим образом (11 Если источник сообщения имеет энтропшо Н(х) (двоичных единиц на букву), то можно закодировать сообщения источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шумов со средней скоростью — е, бу>кв)ее?с, Н (х) (2.5) где в — сколь угодно малая положительная величина.
Передавать их сколь угодно точно со скоростью, больо 1оя >н шей, чем, нельзя. Н (х) Очевидным следствием этой теоремы, применимым к источнику с фиксированной скоростью, является следующее утверждение, 66 Сообщения источника с производите дительностыо Н' х н закодировать так, (двоичных единиц в секунду) можно зак >тобы передавать их сколь угодно то каналу без шумов, при условии, что точно по диск етном Р у Н'(х) (о !оя л>. Это невозможно, если (2.8) Н'(х) >о 1оп . (2 2.7) Этп теоРемы являются частными случаями тео Рассмотрим некоторые простейшие с ния. шие случаи их примене- от прель>пущих в с одинвковыми вер соо щения пезввисимо — «=1оя» 1.
Если к ом 1о ностямн Рзвньпчи 1?1 тогдв вопр»с>у к установлению люб ' ' д Раввине сводится о о тветствия каждого нз элемент лю ым образом взвимн о однозначного Очевидно, что при этом можно пе е ементов соо щения кз символ к у кода у>. о можно перелзввть по квивлу о элементов сообщения в секунду. По о= ,т=)ой,1 Н" Тв обРв" при этих усзоипях теорема справедлива даже зе ипогдн (впрочем без б ередвется без кодировшия. осо ого основшия очи твют, что сооб>щение 2. Пусгь по.прежяему Н=?1 ««= о 1, н число. Построил> все в зм нмволов («кодовые о б озможные после ов д ктельности из кодовых рзвво т". Ус>звони к и инзции» лип " д ой а. Очевидно, их число е соответствие каждого им взаимно одиозпвчно кодовой комбннз ни ция нз а символов, разом кэжтзя комбинз >, нередвннвя по каналу, Рость передачи элеме> л менту сооб> ения пов соо щения б ц и, следовнтельно, ско- а> .=— С С Г а а!ой т («„8) Рвы>м, и в этом сл чве те Тзкнм об узкой код, в о , в кото ом вс у е теорема спревслливз кону>о дл>щу а лаже п и иазыввется инионе и и нмс>от одннве кодовые комбнивцю З- Пусть для т „„.
„, оперным а-Рвзрядным кодо»>~' 'шслн т. Тнк, ивприм е Термин «а- аз обстоятельств, Ркдный кол» обязан своим п он ениом случке ожив предствви оим происхождением т у нь>ни т-ричщ,щи чн„вми ментов вл ивитз источники А тот простой, но отн ' . Колмогоров юдь не тривпзльный щ>иче 6* ох о Ю= у 1ойг 10 (2,9) В данно>> случае знак равенства даже невозможея, так как при целых х н у равенство х !оп>10=у означает, что !очог 1О является рациональным числом, тогда как а денствательности гно иррационально.
Вообще, когда Н=Н „„, но ! не является целой или рапиональной степенью и>, можно для любого числа Ь найти такое число вусть источник выбирает независимо н с равной вероятностью любую из десяти цифр О, 1, „9, а канал имеет два символа (обозначим их 0 н !) и позволяет передавать и символов в секунду. Здесь 1=10. т=2, Н=Н „,.=(опг!0~3332 дв. ед. и С= =о !оп> 2=о. Согласно теореме скорость передачи цифр в таком С канаде может быть сделана сколь угодно Оливкой к и 3,332 Попытаемся достигнуть э>ого, кодируя каждую цифру равномерным а.разрядным кодом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
