2.3. ДИСКРЕТНЫЙ КАНАЛ. СТАТИСТИКА ОШИБОК В ДВОИЧНОМ ДИСКРЕТНОМ КАНАЛЕ

Случайный процесс возникновения ошибок в дискретном канале будет полностью описан, если заданы: входной (А) и выходной (А) алфавиты символов, а также совокупность переходных вероятностей вида , где — произвольная последовательность символов входного алфавита и — символ на входе канала в момент времени — соответствующая а последовательность символов из выходного алфавита, а — символ на выходе канала в момент; - условная вероятность приема последовательности а при условии, что передана последовательность а.

Рис. 2.13 Диаграмма переходов в двоичном канале

Рис. 2.14. Эквивалентная схема дискретного симметричного канала

Число задаваемых переходных вероятностей с увеличением длины входных и выходных последовательностей растет. Так, если используется двоичный код и выходной алфавит равен входному, то при последовательности длины общее число задаваемых переходных вероятностей будет равно . Очевидно, что уже при задание переходных вероятностей в виде таблицы хотя и возможно, но вряд ли целесообразно.

Рассмотрим некоторые математические модели ошибок в дискретном канале, позволяющие достаточно просто рассчитать переходные вероятности для любых последовательностей конечной длины

Дискретный канал без памяти.

Если в любой момент вероятность появления символа на выходе дискретного канала зависит только от символа на входе канала для всех пар символов на входе и выходе, то такой канал называется каналом без памяти. Примером дискретного канала без памяти может служить двоичный симметричный канал (ДСК), граф которого изображен на рис. 2.13. Каждый символ последовательности а на входе с некоторой фиксированной вероятностью q воспроизводится на выходе канала правильно и с вероятностью — неправильно.

Для ДСК легко вычисляется вероятность получения любой последовательности символов на выходе при заданной последовательности на входе. Например, для последовательности длины 3 имеем

Симметричный канал можно представить как канал, к которому подключен источник ошибок (рис. 2.14). Этот источник выдает случайную последовательность ошибок . Каждая позиция , складывается с соответствующей позицией а, в двоичном канале по модулю Там, где в последовательности ошибок стоит 1, передаваемый символ изменится на обратный, т. е. в принятой последовательности будет ошибка. Например, если , то

Переходные вероятности для стационарного симметричного канала принимают

т. е. канал полностью описывается статистикой последовательности ошибок где Последовательность ошибок длины иногда называют вектором ошибок длины . Этот вектор имеет единицы только на позициях, соответствующих неправильно принятым символам. Число единиц в векторе ошибок называют его весом.

На практике при приеме последовательности длины нас часто интересуют вероятности отсутствия и наличия в ней одной, двух и т. д. ошибок. Для ДСК эти вероятности легко вычисляются. Обозначим вероятность того, что среди принятых символов имеется t ошибок в любом сочетании, а через — вероятность одного заданного сочетания ошибок веса I. Тогда найдется как сумма для всех возможных последовательностей ошибок веса t. Следовательно,

где

Каналы с памятью.

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

В общем случае для канала с памятью можно ввести понятие «состояние канала». Тогда каждый символ последовательности на выходе канала будет статистически зависеть как от соответствующего символа на входе, так и от состояния канала в данный момент. Под состоянием канала в заданный момент можно понимать, например, вид последовательности входных и выходных символов вплоть до заданного момента. Так, отражается, в частности, влияние межсимвольной интерференции.

Различают каналы с памятью по входу и каналы с памятью по выходу. Если выходной символ статистически зависит от входных символов , то такой канал называется каналом с памятью по входу. Такой канал характеризуется переходными вероятностями вида . Теоретически память канала бесконечна. Практически число символов, влияющих на вероятности правильного и ошибочного приема символа, ограничено. Память канала может быть определена как число символов N, начиная с которого справедливо равенство условных вероятностей

Последовательность входных символов можно представить как состояние канала момент. Тогда канал будет характеризоваться совокупностью переходных вероятностей вида

Если выходной символ а, статистически зависит от нескольких предыдущих выходных символов, то такой канал называется каналом с памятью по выходу. Переходные вероятности для такого канала записываются в виде

где выходные символы можно представить как состояние канала момент.

Задание канала с памятью с использованием переходных вероятностей вида (2.8) или (2.9) было бы чрезвычайно громоздким. Так, если для канала с межсимвольной интерференцией память по входу ограничивается пятью символами, то число состояний канала будет равно 32. В общем случае, если память только по входу или только по выходу ограничивается в двоичном канале N символами, то число состояний равно Как видно, число состояний растет по экспоненциальному закону в зависимости от длины памяти N. Следует заметить, что некоторые реальные каналы имеют память в десятки, сотни и даже тысячи символов!

Состояния каналов можно различать по вероятности ошибки в каждом из состояний. Изменения вероятности ошибки можно в свою очередь связать с физическими причинами — появлением перерывов, импульсных помех, замираний и т. д. Такой канал можно задать совокупностью переходных вероятностей вида где L — конечное множество состояний канала.

Если предположить, что имеется статистическая независимость между символом а, и состоянием с, при условии, что заданы а, и предыдущее состояние то можно записать:

Рис. 2.15 Эквивалентная схема дискретного симметричного канала при описании его моделью на основе цепей Маркова

Рис. 2.16 Диаграммы переходов при описании дискретного симметричного канала моделью Гильберта: а — из одного состояния в другое; б — возможные исходы передачи в состоянии 2

В этом случае необходимо задать переходные вероятности для состояний канала и вероятности переходов для символов для каждого состояния канала. Таким образом, канал имеет конечное множество состояний, переходные вероятности для которых не зависят от времени. Ошибки в каждом состоянии возникают независимо с постоянной вероятностью. Последовательность состояний является простой цепью Маркова. (Простой цепью Маркова называется случайная последовательность состояний, когда вероятность того или иного состояния в момент полностью определяется состоянием момент). Эквивалентная схема такого канала представлена на рис. 2.15.

Для описания простой цепи Маркова необходимо задать переходные вероятности того, что система в момент перейдет в состояние с, при условии, что в момент она находилась в состоянии и вероятности ошибок в каждом из возможных состояний . В рассмотренной модели канала с памятью состояния канала статистически не зависят от входных и выходных символов. Достоинством такой модели является то, что достаточно большую память канала можно описать относительно малым числом состояний. Увеличивая число состояний, можно более точно описать реальный канал. Однако сложность использования модели в расчетах будет существенно возрастать с увеличением числа состояний.

Простейшей моделью, основанной на применении математического аппарата марковских цепей является модель источника ошибок, предложенная Гильбертом. Согласно этой модели канал может находиться в двух состояниях — хорошем (состояние 1) и плохом (состояние 2).

Первое состояние характеризуется отсутствием ошибок. Во втором состоянии ошибки появляются с вероятностью

Если при передаче элемента а, канал находится в состоянии 1, то при передаче следующего элемента канал будет находиться в том же состоянии с вероятностью и в состоянии 2 — с вероятностью . Если же при передаче элемента а, канал находился в состоянии 2, то при передаче элемента он может находиться в том же состоянии с вероятностью и в состоянии 1 — с вероятностью Матрицу переходов из состояния в состояние обозначим Р:

Если достаточно велики, но не равны между собой, то наблюдается тенденция к сохранению возникшего состояния 1 или 2, что имитирует канал с пакетами ошибок.

На графе (рис. 2.16, а) состояния канала изображены в виде кружков. Направленные стрелки обозначают переходы из одного состояния в другое, число на каждой стрелке указывает вероятность перехода. Для канала, взятого в качестве примера, в состоянии 2 возникают ошибки с вероятностью 0,4 (рис. 2.16,б).

Канал, представленный графом на рис. 2.16, а, имеет тенденцию пребывать в том состоянии, в котором он находится. Большую часть времени канал находится в хорошем состоянии (состояние 1), когда . С вероятностью 10-5 канал переходит в плохое состояние, когда около 0,4 элементов на выходе канала будут ошибочными. Состояние 1 длится в среднем в течение приема 105 элементов, а состояние 2— десяти элементов. Вероятность того, что канал в момент передачи данного элемента будет находиться в том или ином состоянии, зависит от состояния, в котором канал находился при передаче предыдущего элемента. Например, вероятность того, что канал будет находиться в момент приема данного элемента в хорошем состоянии, равна если он в момент приема предыдущего элемента находился в хорошем состоянии, и если он находился в плохом состоянии.

Вероятность появления того или иного состояния определяется из системы уравнений:

где — соответственно вероятности того, что канал находится в состоянии 1 или 2. Отсюда Средняя вероятность ошибки в канале, описываемом моделью Гильберта, определяется выражением

Среднее число элементов на интервале времени, соответствующем плохому состоянию канала (средняя длина пакета ошибок), определяется по формуле

где — вероятность того, что возникшее плохое состояние канала будет распространяться на i переданных элементов. Аналогично можно определить и среднюю длину интервала между ошибками:

где — вероятность того, что хорошее состояние канала будет длиться в течение времени передачи i элементов.

Для выбора кодов необходимо знать вероятность появления t ошибок в кодовой комбинации длиной элементов, которая может быть найдена по формуле

где — вероятность того, что число элементов в кодовой комбинации, переданных за время плохого состояния канала, равно — вероятность появления ошибок в кодовой комбинации при условии, что число элементов кодовой комбинации, переданных за время плохого состояния канала, равно .

Полагая, что в кодовой комбинации длиной элементов возможно появление только одного пакета ошибок, получим

Рассмотренная модель описывается тремя параметрами: которые могут быть найдены экспериментально.

Еще более простая модель источника ошибок, для описания которой достаточно двух параметров и , где а — коэффициент группирования ошибок, предложена в [1.4]. Исследуя статистику ошибок в каналах связи, авторы обратили внимание на то, что график функции в логарифмическом масштабе по обеим осям представляется в виде прямой линии.

Исходя из этого можно записать

Для канала без памяти при все ошибки сосредоточены в виде одного пакета.

Вероятность появления в комбинации ошибок кратности и более может быть приближенно определена по формуле

Описанные выше модели дискретного канала используются для вычисления характеристик систем ПДС. Поэтому при выборе той или иной модели следует прежде всего исходить из требуемой точности расчетов. Разумеется, если имеется несколько моделей, обеспечивающих приемлемую точность, следует выбирать ту из них, которая позволит уменьшить время, требуемое для вычислений, т. е. наиболее простую.