Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 26
Текст из файла (страница 26)
Формула (2.62) справедлива и для примитивного кодирования, когда число символов п в кодовой комби- 130 нации совпадает с числом нпформационцых символов й. Для двоичного постоянного симметричного капала при примитивном кодировании п=й=( и Я„= (1 — р)"= = (1 — р)' и, следовательно, (;1е(Н) = (1 — р)". (2.63) С точки зрения верпосп1 декодирования длинного сообщения две системы связи можно считать эквивалентными, если при достаточном больших г( (,1е1(г!) = =ч'ез(г(), по крайней мере в асимптотическом смысле, т. е. 1нп (), би) (2.64) Я, (л) Здесь индексы 1 и 2 относятся к сравниваемым системам.
Отсюда вытекает возможность характеризовать любую систему связи с любым кодом с помощью вероятности ошибки в эквивалентной ей двоичной системе связи с примитивным кодом. Назовем эквивалентной вероятностью о1иибки р, системы связи величину вероятности ошибки в постоянном симметричном двоичном канале, в котором система с примитивным кодированием оказывается эквивалентной рассматриваемой системе [3!). Эквивалентная вероятность ошибки является удобной мерой для сравнения между собой не только различных кодов, применяемых в одном и том же канале, ью и для сравнения различных систем связи, в которых могут использоваться Различные каналы, различные методы модуляции и организации связи, При любом фиксированном значении А вероятность ошибочного пРиема сигнала, содержащего А двоичных единиц информации, является монотонной функцией эквивалентной вероятности ошибок.
Для системы с блочным кодом эквивалентную вероятность ошибок легко вычислить, если известна вероятность О(п) правильного декодирования кодовой комбипашш, содержащей 1 двоичных единиц информации. Из (2.62) и (2 63) следует Я(п))'= (1 — рз)"', откуда Рз = 1 — [Я (п)]иг = 1 — (1 — а)цг, (2.65) 131 где е=1 --г,г(п) — вероятность ошибочного декодирования кодовой комбинации. ВеличинУ 7,= 1 — р,=(1 — э)п' называют эквивалентной вероятностью правильного приема. При э (<1 Рэ= —; (2.66) Лналогичная величина, названная относительной вероятностью ошибки декодирования, была введена также в работе В.
И. Сифорова [32]. В случае непрерывных кодов, в которых нельзя подразделить последовательность символов на отдельные комбинации (например, в случае цепного кода), эквивалентную вероятность ошибок следует определить с помощью предельного перехода Рэ = — 1 — г7э = — 1 — 1пп [1 — э (!)] ~', (2,67) где е(г) — вероятность ошибочного ггрггелга сообщения, содержащего ! двоичных единиц информации.
Найдем эквивалентную вероятность ошибки для симметричного постоянного канала при кодировании без избыточности кадом с основанием т)2 [ЗЗ, 34]. Еслги вероятность ошибочного приема символа в рассматриваемом канале равна р, то вероятность безошибочного приема последовательности из гг символов равна (1 — Р)э. Такая последовательность содержит г'=)г !аозт двоичных единиц информации. Таким образом, эквивалентная вероятность правильного приема равна г г г<к а3 дэ=(! Р) =-(1 — р) ' 1оя э ггг (приближенное равенство справедливо при р(1), откуда Рэ "= (2.68) 1ояэ т Отсюда следует, например, что канал с т=4 и р= =-10-' эквивалентен па достоверности двоичному каналу с вероятностью ошибок 5 ° 10 ".
132 В качестве другого примера оцепим эквивалентную вероятность оппгбки для описанного выше двоичного систематического кода (7,4). Кодовая комбинация, содержащая я=7 символов и 1=4 двоичных единицы информации, может быть правильно декодирована, если ошибочно принят не более чем один символ из семи. Вероятность правильного декодирования равна р)г+7 (1 р)э Здесь первый член представляет вероятность того, что все символы приняты верно, а второй член — вероятность того, что искажен один символ пз семи.
Эквивалентная вероятность правильного приема равна г7э =--(1 — ) ~ =-](! — Р)'+ 7Р(1 — Р)'! 1 При р«! это выражение можно прпбляжевно записать, пренебрегая высокими степенями р, так: г)э = [1 — 7р+ 21р' — ° + 7р — 42р'+ ° ] '" = = [1 — 21 р'! и" = 1 — 5,25р', откуда эквивалентная вероятность ошибок равна р,= 5,25рэ.
(2.69) Эта выражение можно получить проще, если учесть, что при лр«1 вероятность того, что в симметричном канале будут искажены три нли более символов в комбинации, значительно меныпе вероягпюсти ошибочного приема двух символов. Поэтому вероятность ошибочного декодирования кодовой комбинации е в коде (7„4) в первом приближении равна вероятности ошибочного приема каких-либо двух символов нз семи: .=С,'р (1 — р)э=С,'р =21р, откуда с учетом (2.66) непосредственно следует (2.69), Вообще, если двоичный корректирующий код является плотно упакованным, то рассуждая аналогичным образом, можно показать, что при ггр«! Оэ+г рэ+э 133 Для не двоичных кодов, нсправлнгощих ошпбки кратности г символов и не исправляющих ошибки большей кратности, при симметричном канале приближенная зависимость (2.70) также справедлива. Следует только помнить, что под ( понимается количество информации в кодовой комбинация, выраженное в двоичных единицах.
Выражение (2.68) является частным случаем (2.70) при г=б, так как при любом и Если примененный систематический код обеспечивает возможность исправления ошибки кратности г во всех случаях, а также в некоторых случаях оп!ибки более высокой кратности, то вероятность ошибошюго декодирования кодовой комбинации е при р(<1 прнолизительно равна вероятности того, что произойдет ошиоочньш прием г+1-го символа в одном из неисправляемых сочетаний а — (Сг+ — ог „) Рг+', где аг+г — число исправляемых сочетаний огпибок кратности г+1, откуда (С'„+' " + ) "+'.
(2.71) Из полученных выражений видно, что эффективность корректирующих кодов тем выше, чем меньше вероятность ошибки р в стационарном симметричном канале. Так, например, при р=0,1 эквивалентная вероятность оптибки для кода (7,4) согласно (2.б9) приблизительно равна 0,05, т. е. всего лишь в два раза меньше, чем при примитивном кодировании, тогда как при р=10 — з эквивалентная вероятность ошибки оказывается порядка 5-10-', т.
е. в этом случае повышение верности оказывается весьма существенным. Подводя итог, мои!но отметить, что для объективного сравнения кодов (или систем связи) можно пользоваться либо вероятностью неисправленной ошибки, либо эквивалентной вероятностью ошибки. Первая из этих мер пригодна для систем связи, передающих сообщения, ценность которых не теряется при небольшом ко13ч личестве ошибок, а лишь монотонно уменьшается. Йторая мера удобна в тех случаях, когда каждое законченное сообщение должно быть принято без ошибок, т. е.
когда даже одиночная ошибка по,пностью его обесценивает. Примечания 1 (я й 2.1). Термин схапал с паыятыоэ указывает иа то, что вероятность ошибки в таком канале зависит от того, хая принимались предыдущие символы, т. е. канал иаи бы хранит в своей па.
мята предыдущие собьппя. Говоря о зависимости ошибок в канале с памятью, следует учитывать, что здесь имеется в виду ие причинно-следственная зависимость, а статистическая. Два события А и В считаются невавяснмыми в вероятностном смысле тогда и только тогда, когда р(А(В) =р(А). В противном случае они зависимы, если даже известно, что ови вызываются различными причинами. Пусть, например, в двоичном дискретном запале ошибки вознииают только под воздействием неяотарого источнина помех !у, причем помеха появляется в случайные моменты времени с вероятностью и и существует некоторая вероятность р того, что если Ьй символ передавался при наличии помехи, то к моменту передачи (1+ 1)-го символа помеха прехратнтся (модель Гильберта).
Если условная вероятность ошибки при действии помехи равна рз, то, йая легко подсчитать, среднян безусловная вероятность ошибки равна Вычислим условную вероятность р(1+1(1) ошибочного приема (!+1] го симвоаз при условии, что 1-й символ принят ошибочно. Поскольку 1-й символ принимался в момент присутствия помехи, то с вероятностью () (1+1)-в символ будет принят в отсутствии помехи, т. е. без ошибки, а с вероятностью 1 — р помеха будет продолжаться и при приеме (!+1)-го символа, В последнем случае этот символ может быть принят ошибочно с вероятностью рь Таким образом, р(г+1)1) =р,(1 — р) чьр.
Таким образом, ошябхи в таком канале оказываются зависимгями, хотя причииоа ошибочного приема (!+!)-го символа не является ошибка при приеме предыдущего символа. В постоянном симыетричном канале ошибки независимы. Ках известно, отсюда следует, что появление г ошибок в блоке из и спмволов определяется биномиальным распределением )'-() =С'.р (1 — р)"- . Поэтому всякий симметричный канал, в хотором число ошибок в блоке пе подчиняется бнномяальному распределению, являетсн каналом с памятью. 1йб 2 (к й 2.3).
Можно сформулировать условие однозначной декодпруемасти последовательное<и символов нсравпомерного када. Ллл существования кода, содержащего ! комбинаций, в котором и<— число символов в <-и комбинации, и допускающего однозначное декодирование, необходимо и достаточно условие [40] ~' щ "<(1, (2.72) ч=< "' В широко распространенном советском телеграфном аппарате СТ-35 применены трн регистра — русские буквы, латинские буквы и цифры (включая знаки препинания).
136 где >н — основание кода. Из условия (2.72) можно вывестн теорему кодирования для канала без шуъюв [7]. 3 (к й 2.3). В качестве примера практически используемого меточа кадированнл, приблпз<аюшегося к экономичному, обычно при водят телеграфный код Морзе. Этог пример не очень удачен, так как код Морзе содержит значительную избыточность, хотл при ег<> разработке был использован принцип выбора наиболее коротких камбинацнв для наиболее часта встречающихся букв, В телеграфной практике существует другой поучительный пример использования статистических свойств источника для сокращения среднего числа символов кодовой последовательяости, причем использованы не столька одномерные распределения вероятностей букв, сколько вероятностные свята между передаваемыми знакамн.