книги / Теория информации
..pdfИмеется несколько способов введения количественных характерис тик помехоустойчивости. Рассмотрим сначала способы описания поме хоустойчивости дискретных систем. Эти системы характерны тем, что все возможные сигналы конечной длительности образуют дискретное конечное множество; пусть общее число возможных сигналов равно N. Действие шумов сводится к тому, что некоторые символы в сигнале подменяются другими, в результате чего вместо переданного (например, /-го) сигнала принимается другой (например, &-й) сигнал. Помехоустой чивость системы связи наиболее полно может быть охарактеризована набором вероятностей {Pik} того, что при передаче i-ro сигнала будет принят к-й (i,k = 1,2,...Д); и если мы хотим задать требования к поме хоустойчивости системы с учетом ценности каждого из сообщений в отдельности, то задание всей матрицы {P J необходимо.
Однако сравнение систем по их матрицам {Р.к} (которые можно назвать «стохастическими матрицами трансформации сообщений») связано с рядом затруднений, а часто и не необходимо: достаточно ввести более простые характеристики помехоустойчивости. К таким простым параметрам относится, например, средняя вероятность оши бочного приема, Рошср.:
1 - П ) . 0 1 - 2 )
1=1
где р - вероятность передачи /-го сигнала.
Другим собирательным параметром, характеризующим помехоус тойчивость системы, может служить остаточная средняя неопределен
ность относительно переданного сообщения, т.е. энтропия |
|
||
Я = - ( 1 - Р |
J l o g ( l - P J - P |
logP |
. (11.3) |
Для непрерывных систем связи описание помехоустойчивости требует специфического подхода, так как множество возможных сигналов даже конечной длительности несчетно. Действие шумов в линии связи сводится к тому, что вместо отправленного сигна ла x(t) на выходе премника наблюдается другая функция времени, у((). Чем ближе y(t) к x(t) при заданном шуме, тем более устойчи ва система по отношению к данной помехе. Для количественного описания помехоустойчивости необходимо ввести меру различия двух функций: x(i) и y(t). Чащ е всего в качестве такой меры при нимается средний квадрат разности сравниваемых функций:
Т |
2 |
|
Rx = (х (/) - у (О )' = у J[* (О "У(0 ]dt• |
(11 -4) |
1 о
«Расстояние» между функциями x(t) uy(t) может быть также опре делено с помощью так называемой абсолютной ошибки
Rг= К О - И О7Н
Другим способом является «частотно-взвешенный эффективный кри терий» [4]. Идея этого критерия состоит в том, чтобы придавать различным частотным компонентам разности х и у разные веса. Это эквивалентно пропусканию разности x(t)- y(t) через фильтр с определенной переходной функцией h(t); выходной сигнал такого фильтра выразится как
/ ( 0 = |
( 11.6) |
-Vi |
|
«Расстояние» между функциями х(() и |
y(t) определится как средняя |
мощность сигнала на выходе рассматриваемого гипотетического фильтра:
я,=У//Ч0‘*- |
(11-7) |
1 о |
|
Введенныевыше меры различия отправляемого и принимаемого сигналов могут служить основой для характеристики помехоустой чивости систем. Например, система может считаться достаточно по мехоустойчивой, если «расстояние» между отправленным сигналом и сигналом на выходе системы не превышает заданной величины.
Вкачестве меры помехоустойчивости могут быть приняты и другие числовые характеристики, например, логарифм обратной величины среднеквадратичной ошибки в непрерывном случае, минус логарифм вероятности ошибки в дискретном случае, раз личным способом введенные понятия эквивалентного отношения сигнала к шуму и пр.
11.3.Способы повышения помехоустойчивости информационных систем
Внастоящее время известно большое число способов повышения помехоустойчивости систем.
Простым и часто применяемым способом повышения помехоус тойчивости передачи является увеличение отношения сигнал/помеха за счет увеличения мощности передатчика. Однако этот метод, не смотря на свою простоту может оказаться экономически невыгодным, так как связан с существенным ростом сложности и стоймости обору дования. Помимо того, увеличение мощности передачи сопровождает ся усилением мешающего действия данного канала на другие.
Важным способом повышения помехоустойчивости передачи не прерывных сигналов является рациональный выбор вида модуляции сигналов. Применяя виды модуляции, обеспечивающие значительное расширение полосы частот сигнала, можно добиться существенного повышения помехоустойчивости передачи.
Радикальным способом повышения помехоустойчивости переда чи дискретных сигналов является использование специальных поме хоустойчивых кодов. Такие коды позволяют обнаруживать и устранять искажения в кодовых комбинациях за счет введения в код дополни тельных, избыточных символов. Кодирование сопровождается увели чением времени передачи или частоты передачи символов кода. Это приводит к расширению спектра сигнала.
Ниже рассматриваются основные положения теории помехоус тойчивого кодирования.
Разновидности помехоустойчивых кодов. Высокие требования к достоверности передачи, обработки и хранения информации в сов ременных телекоммуникационных системах диктуют необходимость такого кодирования информации, которое обеспечивало бы возмож ность обнаружения и исправления ошибки.
Кодирование должно осуществляться так, чтобы сигнал, соответс твующий принятой последовательности символов, после воздействия на него предполагаемой в канале помехи оставался ближе к сигналу, соответствующему конкретной переданной последовательности сим волов, чем к сигналам, соответствующим другим возможным после довательностям. (Степень близости обычно определяется по числу разрядов, в которых последовательности отличаются друг от друга.)
Это достигается ценой введения при кодировании избыточности, ко торая позволяет так выбрать передаваемые последовательности символов, чтобы они удовлетворяли дополнительным условиям, проверка которых на приемной стороне дает возможность обнаружить и исправить ошибки.
Коды, обладающие таким свойством, называют помехоустойчи выми. Они используются как для исправления ошибок (корректирую щие коды), так и для их обнаружения.
У подавляющего большинства существующих в настоящее время помехоустойчивых кодов указанные условия являются следствием их ал гебраической структуры. В связи с этим их называют алгебраическими ко дами. (В отличие, например, от кодов Вагнера, корректирующее действие которых базируется на оценке вероятности искажения каждого символа.)
Алгебраические коды можно подразделить на два больших клас са: блоковые и непрерывные.
В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения (или последовательности из к символов, соответствующей этой букве) блока из п символов. В операциях по преобразованию принимают участие только указан ные к символов, и выходная последовательность не зависит от других символов в передаваемом сообщении.
Блоковый код называют равномерным, если п остается постоян ным для всех букв сообщения.
Различают разделимые и неразделимые блоковые коды. При коди ровании разделимыми кодами выходные последовательности состоят из символов, роль которых может быть отчетливо разграничена. Это информационные символы, совпадающие с символами последова тельности, поступающей на вход кодера канала, и избыточные (прове рочные) символы, вводимые в исходную последовательность кодером канала и служащие для обнаружения и исправления ошибок.
При кодировании неразделимыми кодами разделить символы выход ной последовательности на информационные и проверочные невозможно.
Непрерывными (древовидными) называют такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделе ния ее на независимые блоки. Непрерывные коды также могут быть разделимыми и неразделимыми.
Наиболее простыми в отношении технической реализации кодами этого класса являются сверточные (рекуррентные) коды.
П ринципы помехоустойчивого кодирования блоками конечной длины . Пусть некоторая последовательность элементарных символов, содержащая п разрядов, представляет кодовое слово. Если в любом из
разрядов кодового слова возможное число различных элементарных символов составляет т, можно построить код, состоящий из т слов. В том случае, когда все возможные кодовые слова используются для пере дачи сообщений от источника, код называется простым (примитивным) или кодом без избыточности. Такой код испол ьзовать для кодирования в канале с помехами нецелесообразно. Для придания коду корректирую щих свойств в него необходимо ввести избыточность, т.е. использовать
для передачи сообщений лишь часть М из числа т" кодовых |
слов. |
|
Количественно |
избыточность кода по аналогии с величиной избыточ |
|
ности источника сообщений может быть определена как %= |
1 - log |
|
М/(п log т); при |
этом величину 1 - х = log М/(п log т) = R называют |
относительной скоростью кода. Число т в теории кодирования называ ют основанием кода. Простейшими и в то же время наиболее широко используемыми на практике являются двоичные коды, у которых т - 2.
Возможность использования в системе связи кодовых блоков, име ющих одинаковую длительность, существенно упрощает технику пе редачи дискретных сообщений. Множество всех возможных кодовых блоков длины п можно представить векторами линейного пространс тва размерности тп, если под операцией сложения понимать поразряд ное сложение по модулю т. В частности, при т = 2, когда символами кода являются 0 и 1, в линейном пространстве можно ввести широко используемое в теории кодирования понятие - расстояние Хемминга между кодовыми блоками, под которым понимается поразрядная разность (или сумма) по модулю 2 между двумя любыми векторами пространства 2". Расстояние Хемминга оказывается равным числу раз рядов, в которых символы этих кодовых блоков не совпадают.
Расстояние Хемминга между кодовыми блоками позволяет ввести еще один важный параметр в теории кодирования.
Определение. Наименьшее из расстояний Хемминга между лю быми парами используемых кодовых слов называется кодовым рас стоянием для кода К и обозначается через d(K).
Рассмотрим принципы помехоустойчивого кодирования на основе блочных равномерных кодов, полагая, что в системе связи принятие ре шения о переданном сообщении осуществляется по результатам распоз навания каждого кодового слова из переданной последовательности. При использовании кода без избыточности (примитивного кода, для которого d{K) —1) появление ошибки в любом из принятых слов останется неза
меченным, поскольку трансформация символа хотя бы в одном разряде приводит к используемому кодовому слову. Возможность фиксации ошиб ки в кодовом слове появляется только в том случае, когда в процессе ко дирования вводится определенная избыточность. Как уже отмечалось, в этом случае из возможного N = т" числа кодовых блоков для передачи сообщений от источника используются лишь часть М < N кодовых слов. Будем называть используемые для кодирования блоки разрешенными, а остальные (N - M ) блоков - запрещенными. В отсутствие помех на выходе канала могут появиться только разрешенные блоки. При передаче по кана лу с помехами часть кодовых символов может быть принята с ошибками, при этом чаще всего принятый кодовый блок оказывается запрещенным, что свидетельствует о наличии ошибки при передаче.
Существует ненулевая вероятность того, что комбинация ошибочно принятых символов преобразует переданное слово в другое разрешенное и наличие ошибки останется незамеченным. Разумеется, при разработ ке помехоустойчивого кода стремятся к тому, чтобы вероятность такого события оказалась весьма малой. При декодировании с исправлением ошибок принятые запрещенные кодовые блоки преобразуются декодером в разрешенные по определенным правилам, установленным для данной системы. Эти правила зависят от свойств канала связи и определяются в соответствии с выбранным статистическим критерием. В частности, та ковым может быть правило исправления ошибочно принятого блока в на иболее вероятный разрешенный. Конечно, может оказаться, что наиболее вероятный кодовый блок не соответствует переданному слову. Тем не ме нее, при удачно разработанном коде достаточно большой избыточности может быть обеспечена высокая вероятность исправления ошибки.
При декодировании с исправлением ошибок можно воспользоваться
-»
определением кода как множества М пар, состоящих из кодовых слов Ь,
и соответствующих им групп Bi, запрещенных блоков. Таким образом, все множество N последовательностей конечной длины п разбивается на Мнепересекающихся подмножеств. Если принятый кодовый блок прина длежит подмножеству Bj, принимается решение, что передавалось кодо-
вое слово 6,. Очевидно, что при декодировании по критерию максимума правильной вероятности в подмножество Bj, помимо слова bj, необходимо включить все те запрещенные кодовые блоки, при приеме которых наибо лее вероятным является разрешенное кодовое слово bj.
Выбор наилучшего правила, по которому осуществляется декоди рование с исправлением ошибки, зависит от специфических свойств
канала передачи. Действительно, границы между подмножествами Я ,, при которых обеспечивается максимум правильной вероятности ис правления искаженного блока, могут существенным образом зависеть от статистических характеристик канала передачи. Рассмотрим проце дуру выбора правила исправления ошибок на примере симметричного канала без памяти. Допустим, что в результате прохождения по такому
каналу кодового слова Ъ, из-за воздействия помех в q разрядах про изошла ошибка, в результате чего на выходе канала был принят блок
bj• Пусть d(i,j) есть расстояние Хемминга между блоками bi и bj\ так что q = d(i,j). Тогда вероятность перехода на выходе канала слова Ы в
блок bj
( 11.8)
Отсюда следует, что в двоичном симметричном канале без памяти при заданных п и т вероятность p (b j |й(.^ зависит только от рассто яния d(i,j)- Отметим, что при вероятности ошибочного приема одно го разряда р < 0,5 значение вероятности (11.8) монотонно убывает с увеличением расстояния d(i,j). Следовательно, вероятность приема блока тем меньше, чем больше его расстояние от переданного слова
. Если в качестве правила принятия решения о переданном слове при декодировании с исправлением ошибки в симметричном канале без памяти выбрать правило декодирования по максимуму вероятности
р ^Ь. |5.^, то в таком канале ошибочный блок bj следует декодировать как разрешенное кодовое слово bt , которое находится на наименьшем расстоянии от />у. . Декодирование по наименьшему расстоянию (на зываемое также алгоритмом Хемминга) при равновероятной передаче всех кодовых слов является оптимальным для симметричного канала без памяти.
При таком алгоритме декодирования исправляющая способность кода характеризуется следующей теоремой.
Код К при декодировании по наименьшему расстоянию исправля ет любые q и менее ошибок в каждом кодовом слове тогда и только тогда, когда кодовое расстояние d(K) >2q + 1.
Покажем, что действительно переданное слово Л, при d(K) > 2q+l по расстоянию оказывается ближе к принятому блоку b j, чем любое другое кодовое слово. Допустим обратное, т.е. существует кодовое
слово Ьк , для которого d(k,j) < d(i,j). Тогда в соответствии с теоре мой треугольника справедливо следующее неравенство: d(k, i) < d(k,j) + d(i,j), или d(k,i) < 2d(i,j). Однако по условиям теоремы d(i,j) < q < d(K)/2 и, следовательно, d(k,i) < d(K), что противоречит определению кодового расстояния.
Обратно, пусть кодовое расстояние d(K) = d <2q и b, , b} - такие
кодовые слова, что d(i,j) = d. Тогда, заменив в Ы q разрядов на соот ветствующие разряды из bj, получим вектор Ьк , для которого d(i,k) = q, d(k,j) = d - q < q . Отсюда следует, что d{i, к) = q, d(k,j) < q. Следо
вательно, при декодировании слово bk может быть отождествлено со
словом bj и ошибка не будет исправлена.
Отметим большую значимость кодового расстояния d(K) как ос новного показателя исправляющих возможностей кода. Поскольку вероятность появления каких-либо ошибок кратности q определяется биномиальным законом
p ( q ) = C W ( l - p f ' \ |
(11.9) |
оказываются справедливыми следующие оценки вероятности оши
бочного декодирования podпри исправлении ошибок: /;
P o d * |
Z |
P f a ) |
|
Н “( П / 2 ] |
( И . Ю ) |
Задача помехоустойчивого кодирования состоит в поиске кода, обладающего максимально достижимым кодовым расстоянием d(K), или, точнее, максимизации кодового расстояния при задан ных п - числе символов в кодовом слове, и М —числе кодовых слов. Несмотря на то, что для многих значений п и М величина макси мально достижимого d[K) получена, в общем виде задача помехо устойчивого кодирования решения не имеет. Реализация процеду ры помехоустойчивого кодирования на первый взгляд не вызывает труда. В память кодера записываются кодовые слова и правило, по которому каждое из состояний источника отождествляется с соответствующим словом, посылаемым в канал. Это правило из
вестно и на декодере. Декодер, приняв блок, искаженный поме хой сравнивает его со всеми М кодовыми словами и отыскивает то из них, которое по хемминговому расстоянию ближе остальных к принятому блоку. Можно показать, однако, что даже при уме ренных и этот алгоритм декодирования на практике не реализуем из-за гигантского объема необходимой памяти и соответствующей системы логической обработки. Поэтому применение достаточно эффективных кодов при табличном методе кодирования и декоди рования технически невозможно. Это приводит к тому, что одним из основных направлений современной теории кодирования явля ется поиск таких кодов, для которых кодирование и декодирование осуществляются не перебором таблицы, а в результате определен ных регулярных правил, основанных на алгебраической теории. К числу таких кодов относятся линейные блочные, в частности,
циклические коды.
Наиболее характерной ситуацией использования кодирования является передача дискретных сообщений в реальном времени при огра ниченной мощности передатчика. Это означает, что «-символьное ко довое слово должно быть передано за время, равное времени выдачи к символов источником сообщения. Если это условие не выполняется, то кодирование не имеет смысла, поскольку последовательность пере даваемых символов сообщения может быть считана с меньшей скоро стью и в результате характеристики помехоустойчивости могут быть
за счет увеличения энергии передаваемых символов. Пусть мощность передатчика равна Р, а длительность сообщения,
содержащего к символов, равна Tw. Тогда энергия сигнала, приходяща яся на слово сообщения, равна PTw.
В случае блокового избыточного кодирования имеющаяся энергия распределяется на п символов, поэтому энергия, приходящаяся на кодо вый символ, равна РГ / п. Так как п > к, то при использовании кодирова ния энергия, приходящаяся на символ, уменьшается. Это приводит к тому, что в системе с избыточным кодированием вероятность ошибки на символ оказывается "Выше, чем в системе без кодирования. Если код обладает вы сокой корректирующей способностью, то благодаря наличию избыточных символов эти потери «отыгрываются» и обеспечивается дополнительный выигрыш, который принято называть энергетическим выигрышем коди рования (ЭВК). ЭВКявляется количественной мерой эффективности ко-
дирования. Его значения оценивают, сопоставляя энергетические затраты на передачу одного бита при фиксированных вероятностях ошибочного приема либо символа, либо бита сообщения в системах с кодированием и без кодирования.
Контрольные вопросы
1.Какие критерии применяются для оценки помехоустойчивости систем передачи информации с непрерывными сигналами?
2.Какие критерии применяются для оценки помехоустойчивости систем передачи информации с дискретными сигналами?
3.Перечислите известные способы повышения помехоустойчи вости передачи.
4.Какие коды называют помехоустойчивыми?
5.За счет чего помехоустойчивый код получает способность обна руживать и исправлять ошибки?
6.Что подразумевают под кратностью ошибки?
7.Как определяется минимальное кодовое расстояние?
8.Запишите соотношения, связывающие минимальное кодовое расстояние с числом обнаруживаемых и исправляемых ошибок.
9.Назовите основные показатели качества корректирующего кода.