Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 110
Текст из файла (страница 110)
Поскольку при х«1 1п(1 — х) = — х, из выражения (11.3) получим ! но ра й 1! — Роо) (11.4) Отсюда следует, что верность передачи в системе с переспросом зависит не только от верояпюсти необнаруженной ошибки, как полагают некоторые авторы, но и от вероятности обнаруженной ошибки. Если последняя очень близка к единице, то эквивалентная вероятность ошибки может во много раз превысить Риш * Это может иметь место в канале без замираний, а также в канаде с достаточно быстрымв замираниями, если кодовые комбинации иасчолысо длинные, что ошибки в соседиих комбинациях ярчктичсски иекоррелироваииы.
44 †24 677 сообщения такая же, как и в рассматриваемой системе. Пусть в простейшей системе с переспросом Рос и Рн, постоянны", а в обратном канале ошибки отсутствуют. Предположим, что получателю выдано У информаГМ1 ционпых символов (У~) й), т. е. ~ — '' 1 кодовых комбина!л'з ! ций. Для этого в канал должно быть послано ~ — ~ ! — роо кодовых комбинаций.
Безошибочный прием обеспечивается только в том случае, если ни одна пз посланных комоинацпй не оказалась принятой с необнаруженной ошибкой. Следовательно, вероятность безошибочного приема Ю информационных символов равна Иногда представляет интерес величина остагочнойвероятности ошибочного приемо кодовой комбинации Рн„. Под этим понимается вероятность того, что комбинация, выданная получателю, содержит хотя бы одну ошибку.
Из (11А) видно, что Рнн г — Р„ Можно, однако, показать, что это выражение является точным. Действительно ошибочная комбинация может быть передана потучателю, если прн первой ее передаче она принята с необнаруженной ошпокой либо если она принималась гп раз с обнаруженными ошибками (где т — любое число), а затем принята с необнаруженной ошибкой. Следовательно, г Р, =-Рнн+Рн„рн„+Р Р„„-1-... = Рно оо ! — Р„ (11.5) н|=н До сих пор мы полагали, что сигналы подтверждения и переспроса в обратном канале принимаются безошибочно.
Учитывая, что скорость передачи информации в обратном канале много меньше, чем в прямом, можно закодировать сигналы подтверждения и переспроса так, чтобы вероятность их ошибочного приема была очень мала. Тем нс менее в реальных каналах она все гке не равна нулю, в необходимо учитывать возхюжность того, что сигнал подтвсрждения будет принят как переспрос, пли наоборот. Прн этом возникают специфические ошибки в принятой информации, заклгочаюьциеся в том, что кодовая комбинация будет направлена получателю дважды (прн ошибочном приеме подтверждения) либо будет пропущена (прн ошибочном приеме переспроса).
Для борьбы с такими выпадениями и вставками г, системе с переспросом предлагались различные методы. Г1очти все онп основаны на гам, что в обратном канале устанавливается несгимметричное правило декодирования, при котором вероятность ошибочного приема переспроса ничтожно мала, за счет увеличения верояг- 678 ности ошибочного приема подтверждения. Так, если сигнал подтверждения представлен кодовой комбинацией нз и нулей, а сигнал переспроса — из и единиц, то можно условиться декодировать как переспрос любую принятую по обратному каналу комбинацию, содержащую хотя бы одну единицу.
Для того чтобы участившиеся ошибки при передаче подтверждения не вызвали выдачи получателю лишних кодовых комбинаций, предлагалось хпюго различных методов. Так, могкно каждую кодовую комбинацию снабдить номером. Тогда лишняя повторяемая кодовая комбинация будет иметь тот гке номер, что и ранее принятая.
Еще проще добавлять к каждой кодовой комбинации опознавательные символы, указывающие на то, передается лп данная комбинация впервые илп повторяется. Если на декодер поступит повторная комбинация, а перед этим переспроса не было, то она стирается и не поступает к получателю. Другой метод [61 заключается в том, что всякая принятая разрешенная кодовая комбинация сравнивается с предыдущей и, если они совпадают, стирается. Если же в передаваемом сообщении содержатся две одинаковые комбинации подряд, то вместо ее повторения посылается специальная комбинация (обозначим ее Х), выделенная из числа разрешенных комбинаций. Так, если нугкно дважды повторить комбинацию Л, то передается не АЛ, а ЛХ.
Если нужно передать, например ААААА, то посылают ЛХЛХЛ. При этом никогда в канал не будут посылаться две одинаковые комбинации подряд. Заслуживает упомннания также метод различения первичных и повторных сигналов по дополнительному модулируемому параметру [241. Все этн методы, как легко видеть, требуют некоторого увеличения избыточности. Оценки вероятностей ошибок Прежде чем перейти к описаншо других разновидностей систем с переспросом в дискретном канале, остановимся на вычислении вероятностей обнаруженных и необнаруженных ошибок. Будем полагать прп этом, что параметры канала постоянны либо меняются медленно, так что на протяжении длительности одной кодовой 44н 679 комбинации вероятность р ошибочного приема символа можно считать постоянной, либо, наконец, параметры канала меняются очень быстро, или применены ме!олы декорреляпии ошибок, так что ошибки в пределах комбинации практически независимы и определяются некоторой средней вероятностью р.
Лаже при таких упрощающих предположениях вычислить вероятность необнаругкенной ошибки не всегда удается. Конечно, при малом объеме кода можно перебрать все образцы ошибок, переводящих одну разрсш аную комбинацию в другую, и вычислить их совместную вероятность. Для групповых кодов задача несколько облегчается тем, что если некоторый образец ошибки вызывает необнаруженную ошибку, то он совпадает с одной из кодовых комбинаций. Это видно из того, что групповой код содержит комбинацию, состоящую из одних нулей, и для того, чтобы она перешла в какую-либо из разрешенных кембинаций, необходимо и достаточно, чтобы ошибки произошли в тех разрядах, в которых эта комбинация содержит единицы, Из свойств симметрии группового кода следует, что этот же образец вызовет необнаруженную ошибку при передаче любой кодовой комбинации.
Поэтому для вычисления Р„„при двоичном групповом коде достаточно знать список весов кода, т. е. число кодовых комбинаций йгь имеющих вес (количество единиц) !. Очевидно, что вероятность возникновения образца ошибки, совпадающего с одной из кодовых комбинаций, равна (11.5) К сожалению, список весов вычисляется аналитически только для кодов Хех!ыинга с г(=3 и !(=4 [13), а также для кодов Рида †Мюлле (28). Для других кодов его можно определить только перебором всех комбинаций, что практически возможно лишь прп небольшом объеме.
Так, при 1=20 число кодовых комбинаций превышае~ 10' и такой перебор возможен только с помощью электронной вычислительной машины, а прн А=40 эта задача становится непосильной и для машины, хотя для циклических кодов с Й>40 кодер и декодер, обнаруживающий ошпбки, вполне выполнимы. 680 Лля колов с большим и и А приходится пользоваться только опенками для Р„,. Некоторые такие оценки приведены в !14]. Если помимо л и А известно минимальное хеммингово расстояние !1! „=21+1, то удобно пользоваться оценками (15): (11,7) Вторая из этих оценок более точна, но требует при больших л вычислений на машине.
Представляет интерес значение Р„,(0,5) — вероятность необнаруженной ошибки в двоичном канале при р=0,5, т. е. при полном обрыве связи, В этом случае на выходе реша!ошей схемы с равной вероятностью возникает любая последовательность кодовых символов и вероятность необнаруженной ошибки равна отношению числа разрешенных комбинаций Ля к общему их числу й!: Р„„(0,5) =- У+ В частности, для (л, А)-кода, й!=2" п й!=.2!, откуда Рвь(0,5) =2 (" Ы. (11.8а) При большой разности (гг — А) вероятность необнару>кенной оп!ибкн при обрыве связи может быть весьма малой, например Р!!,<1О в, если л — 1=20. Конечно, при этом информация передаваться не может, так как из-за большого значения Р,„ эквивалентная вероятность ошибки р;,=0,5.
Однако благодаря малой величине Р„ такая система допускает относительно длительные обрывы связи, в течение которых получателю не вьщается ложная информация. Это является одним из основных достоинств рационально построенной системы с обратной связью. Что касается вероятности обнаруженной ошибки Р„, то ее приближенное значение легко получить из 68! раа рне рсст! а ! Р.„- 1 — (1 — р)-.
(1! .9) а! а гр а та' Система с блокировкой тР-а 10 !О !Р !Р Ю СР Р аа' ню' остт а лгта та -а !Р-а га-' р (11.! 0) Рпс. 11.! Основные параметры спстемы с пере- спросом прн коне Хев!лгпнга (7, 4). Рнс. 11гс Основные параметры снстемы с переспросом прп коде Ботва — Чоупкурн (63, 45). (11.1), если учесть, что 6)= (1 — р), а Р,«Р„. Последнее неравенство выполняется при любом разумном коде, так как в противном случае применение системы с вереспросом потеряло бы смысл.
Таким образов!, На рис. 11.! показаны зависимости Р„, Р„„Р„, и ра от р, вычисленные по формулам (113), (11.6), (11.5), (!1.4) для кода Кемнпнга (7.4). Такие же завпситюсти для кода Боуза — Чоудхури [65, 43) показаны на рис. 11.2, где вместо неизвестных точных значений Р, использовались оценки (!1.7), так что значения Рост и р, завышены. К обсуждению этих результатов мы еще вернемся. Описанная выше простейшая система с переспросом является простой только в смысле принципа построения. Осуществление же ее связано с серьезными трудностями, возникающими вследствие конечности времени передачи и распространения сигналов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
